Mysql索引原理

說起Mysql就離不開SQL優(yōu)化，說起優(yōu)化就離不開索引，那么什么是索引？為什么加了索引就可以快？那接下來我們就一起來探討一下索引相關(guān)的知識！

一、數(shù)據(jù)結(jié)構(gòu)中常見的索引

【對這塊數(shù)據(jù)結(jié)構(gòu)了解的同學建議跳過本節(jié)】

1.二叉樹

說起二叉樹，我們都知道每個結(jié)點最多只能有兩個子結(jié)點，例如：

可以發(fā)現(xiàn)二叉樹很有規(guī)律，左子結(jié)點小于當前結(jié)點，右子結(jié)點大于當前結(jié)點。那這樣不是查詢起來很方便呢？二叉樹的性質(zhì)決定了它的時間復雜度為 Olog(n)，當然，二叉樹的時間復雜度與它的插入順序有著，如果按升序或降序的方式插入數(shù)據(jù)，那么它的二叉樹的高度h就與結(jié)點個數(shù)相等了，此時復雜度就提高到了O(n)。

假如，數(shù)據(jù)庫使用二叉樹來做索引，此時需要插入1000條數(shù)據(jù)，我們來計算一下這樹的高度。（深度為k的二叉樹最少有k個結(jié)點，最多有2^k-1個結(jié)點）

2^10-1 ≈ 1000    此時樹的高度約為10
最差的情況，樹的高度為1000

樹的高度決定了查詢的效率，而二叉樹又會存在高度10~1000這么大的差距，很明顯它已經(jīng)不適合做我們的索引了！

2.平衡樹

前面把問題擺出來了，二叉樹的高度很不穩(wěn)定，那我們能不能把高度穩(wěn)定一下呢？這就是平衡樹，它會根據(jù)插入的情況，動態(tài)的調(diào)整二叉樹的高度（左右子樹的高度最多差1），比如：我們插入從10，9，8，，，1

看，我沒有騙你吧，它會根據(jù)插入的情況調(diào)整樹的高度，具體怎么調(diào)整的，我只簡單說明一下吧，畢竟不是本文的重點。

平衡樹的調(diào)整分四種情況：

LL、LR、RL、RR

這種情況很好理解

這種情況就是，先將5與6結(jié)點左旋轉(zhuǎn)，然后轉(zhuǎn)成了LL型，再右旋轉(zhuǎn)。
好了，另外兩種就不說了，和這兩種的旋轉(zhuǎn)方式正好相反而已。

咳咳，回到正題，現(xiàn)在好了，平衡樹足以保證了樹的平衡，那么使用它來做索引有沒有 問題呢？
假如我們有100000 條記錄，那么根據(jù)二叉樹的性質(zhì)，樹的高度最低約為2^16，也就是查找一個元素需要查找16次，有同學可能說，嗯，查詢16次我可以接受了，那么假如插入或刪除數(shù)據(jù)呢？AVL樹的最大缺點就是插入結(jié)點時，樹需要頻繁的旋轉(zhuǎn)調(diào)整結(jié)點，所以平衡樹也不太適合做索引。

3.紅黑樹

前面說了平衡樹對二叉樹的要求，左右子樹的高度最多差1，插入數(shù)據(jù)稍有不慎就會造成平衡樹的轉(zhuǎn)換操作，而轉(zhuǎn)換又是非常耗時的一件事情。
而紅黑樹的出現(xiàn)就是為了避免平衡樹的頻繁轉(zhuǎn)換結(jié)點操作。紅黑樹 并不追求 完全平衡 它只要求部分結(jié)點達到平衡，降低了對旋轉(zhuǎn)的要求，從而提高了性能。先看下紅黑樹的定義吧！

*   每個結(jié)點要么是紅的要么是黑的。  
*   根結(jié)點是黑的。  
*   每個葉結(jié)點（葉結(jié)點即指樹尾端NIL指針或NULL結(jié)點）都是黑的。  
*   如果一個結(jié)點是紅的，那么它的兩個兒子都是黑的。  
*    對于任意結(jié)點而言，其到葉結(jié)點樹尾端NIL指針的每條路徑都包含相同數(shù)目的黑結(jié)點。 

插入或刪除元素時，也是需要維護紅黑樹結(jié)構(gòu)的，之所以索引也不使用紅黑樹主要是二叉樹保存大量結(jié)點的時候，會導致樹的高度不斷增加。比如1億個節(jié)點，樹的高度就會達到27層左右，而一般索引又是保存到磁盤中的，如果每次查詢都需要一次IO的話，那也就是需要27次IO操作，而每次IO操作都是非常耗時的。

4.B樹

平衡樹、紅黑樹都是二叉樹，當二叉樹保存大量元素的時候會導致樹的高度不斷增高，那可不可以使用多叉樹呢？

先來看下B樹的定義：

1、B樹的組成
    關(guān)鍵字（可以理解為數(shù)據(jù)）
    指向孩子節(jié)點的指針

2、B樹的性質(zhì)：
* 若根結(jié)點不是終端結(jié)點，則至少有2棵子樹
* 除根節(jié)點以外的所有非葉結(jié)點至少有 M/2 棵子樹，至多有 M 個子樹（關(guān)鍵字數(shù)為子樹減一）
* 所有的葉子結(jié)點都位于同一層

5.B+樹

B+樹與B樹的區(qū)別主要在于：

* 節(jié)點的子樹數(shù)和關(guān)鍵字數(shù)相同（B 樹是關(guān)鍵字數(shù)比子樹數(shù)少一）
* 節(jié)點的關(guān)鍵字表示的是子樹中的最大數(shù)，在子樹中同樣含有這個數(shù)據(jù)
* 葉子節(jié)點包含了全部數(shù)據(jù)，同時符合左小右大的順序

B+樹相比B樹的優(yōu)點再于：層級更低，葉子結(jié)點形成鏈表，范圍查詢方便；

二、Mysql中的B樹與B+樹

1.磁盤讀取原理

索引文件一般以文件的形式存在磁盤上面，索引檢索操作需要磁盤的IO，但是磁盤順序讀取的效率很高，所以在讀取的時候，磁盤往往不是按需讀取，而且每次都會預讀，即使只需要一個字節(jié)，磁盤也會從這個位置開始，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。由于磁盤順序讀取的效率很高，因此對于具有局部性的程序來說，預讀可以提高IO效率。預讀的長度一般為頁的整數(shù)倍（頁是計算機管理存儲器的邏輯塊，操作系統(tǒng)往往將主存和磁盤存儲區(qū)分割為連續(xù)的大小相等的塊，每個存儲塊稱為一頁，大小通常是4K）主存和磁盤以頁為單位交換數(shù)據(jù)。當程序要讀取的數(shù)據(jù)不在主存中時，會觸發(fā)一個缺頁異常，此時系統(tǒng)會向磁盤發(fā)出讀盤信號，磁盤會找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁或幾頁載入內(nèi)存中，然后異常返回，程序繼續(xù)運行

2.Innodb中的B+樹

Innodb中使用是B+樹作為索引，比如下圖中的主索引：

葉子結(jié)點包含了所以的結(jié)點，除了葉子結(jié)點之外，其它結(jié)點不包含值，而葉子結(jié)點包含具體的值

二級索引
Innodb中的二級索引，也是一棵B+樹，只是它的葉子結(jié)點指向的是主索引中的主鍵值，然后再去主索引中查找具體的值；

3.myISAM中的B+樹

MyISAM引擎使用B+樹作索引時，結(jié)構(gòu)與Innodb大致相同，只是它葉子結(jié)點存放的不是具體的記錄值，而是記錄的地址。

二級索引
一級索引中，MyISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址，而二級索引在結(jié)構(gòu)上沒有任何區(qū)別，二級索引也是直接指向記錄的地址。