????????索引就像一本書的目錄，通過索引可以快速找到我們想要找的內(nèi)容。那么什么樣的數(shù)據(jù)結(jié)構(gòu)可以用來實(shí)現(xiàn)索引呢？我們可能會想到：二叉查找樹，平衡搜索樹，或者是B樹等等一系列的數(shù)據(jù)結(jié)構(gòu)，那么為什么MySQL最終選擇了B+樹作為索引的數(shù)據(jù)結(jié)構(gòu)呢？

索引的“要求”

? ? ? ? 要想知道什么樣的數(shù)據(jù)結(jié)構(gòu)最適合索引，首先我們要知道索引需要什么？

????????首先，數(shù)據(jù)庫的索引時保存在磁盤上的，因此我們在查詢索引的時候，要先去磁盤上讀取索引到內(nèi)存，然后再通過索引找到要訪問的數(shù)據(jù)，最后再去磁盤中讀取數(shù)據(jù)，整個過程中會發(fā)生多次IO，那么我們自然希望發(fā)生磁盤IO的次數(shù)越小越好，這樣可以提高數(shù)據(jù)查詢的效率。

????????其次，MySQL是支持范圍查找的，所以我們希望通過索引可以進(jìn)行高效的范圍查找。

二叉查找樹

二叉查找樹可以在logN的時間內(nèi)找到目標(biāo)值，那么二叉查找樹適合用作索引嗎？

答案是不適合

????????首先，二叉查找樹存在極端情況，如果每次插入的結(jié)點(diǎn)都是最小或者最大的，那么二叉查找樹就會退化成鏈表，查詢的時間復(fù)雜度就從O(logN)降到了O(N)

? ? ? ? 其次，如果索引的數(shù)量很多，樹的高度也會變得很高，磁盤需要的IO次數(shù)也會不斷增加。

平衡二叉樹

?????????平衡二叉樹相比于二叉查找樹加上了一個條件：左右子樹高度差不能超過1；雖然這個條件避免了原先二叉查找樹中極端情況下會退化成鏈表的問題。

? ? ? ? 但是同樣的，當(dāng)樹中的結(jié)點(diǎn)不斷增加的時候，樹的高度高度也會不斷增加，同樣會使得IO次數(shù)不斷增加。

B樹

? ? ? ? 實(shí)際上，二叉查找樹和平衡二叉樹不適合作為索引的數(shù)據(jù)結(jié)構(gòu)，究其本質(zhì)還是因?yàn)樗麄兪嵌鏄洌谑俏覀兛梢钥匆幌耺叉樹的一些數(shù)據(jù)結(jié)構(gòu)，比如B樹。

? ? ? ? B樹不再限制一個節(jié)點(diǎn)就只能有2個子節(jié)點(diǎn)，而是允許M個子節(jié)點(diǎn) (M>2)，從而降低樹的高度。B樹的每一個節(jié)點(diǎn)最多可以包括M個子節(jié)點(diǎn)，M稱為B樹的階，所以B樹就是一個多叉樹。

? ? ? ? 使用了多叉樹的數(shù)據(jù)結(jié)構(gòu)以后，就解決了傳統(tǒng)二叉查找樹中隨著索引數(shù)量的增多，IO次數(shù)會變高的問題。在實(shí)際使用中，只要M大于100，即便是千萬級的數(shù)據(jù)量，仍然可以保證在3-4次IO內(nèi)就找到數(shù)據(jù)。相比與傳統(tǒng)的二叉樹，多叉樹會更加矮胖，更適合作為索引的數(shù)據(jù)結(jié)構(gòu)。

但是，MySQL仍然沒有選擇B樹，為什么呢？

????????首先，B樹的每個節(jié)點(diǎn)都包含數(shù)據(jù)（索引+記錄），而用戶的記錄數(shù)據(jù)的大小很有可能遠(yuǎn)遠(yuǎn)超過了索引數(shù)據(jù)，這就需要花費(fèi)更多的磁盤 I/O 操作次數(shù)來讀到真正需要的索引數(shù)據(jù)信息。

????????其次，MySQL是支持范圍查詢的，B樹進(jìn)行范圍查詢需要進(jìn)行樹的中序遍歷，需要使用遞歸或者迭代搜索來進(jìn)行遍歷，效率不高。

B+樹

最后，MySQL選擇了B+樹，B+樹的結(jié)構(gòu)大致如下所示：

B+樹和B樹很相似，差異如下：

• 葉子節(jié)點(diǎn)（最底部的節(jié)點(diǎn)）才會存放實(shí)際數(shù)據(jù)（索引+記錄），非葉子節(jié)點(diǎn)只會存放索引

• 所有索引都會在葉子節(jié)點(diǎn)出現(xiàn)，葉子節(jié)點(diǎn)之間構(gòu)成一個有序鏈表；

?這樣就解決了B樹的兩個缺陷。

????????B+樹的非葉子節(jié)點(diǎn)不存放實(shí)際的記錄數(shù)據(jù)，僅存放索引，因此數(shù)據(jù)量相同的情況下，相比存儲即存索引又存記錄的B樹，B+樹的非葉子節(jié)點(diǎn)可以存放更多的索引，因此B+樹可以比B樹更矮胖，查詢底層節(jié)點(diǎn)的磁盤 I/O次數(shù)會更少。

????????B+樹所有葉子結(jié)點(diǎn)使用雙向鏈表連接，這使得其進(jìn)行范圍查找的時候，十分方便，相較于B樹范圍查詢效率更高。

總結(jié)

為什么采用B+樹作為索引的數(shù)據(jù)結(jié)構(gòu)？

1.和傳統(tǒng)的二叉查找樹相比，B+樹是一棵多叉樹，樹的高度更小，整個樹更加矮胖，查詢的效率更高；二叉樹的話，數(shù)據(jù)量上去了樹的高度就會很高。

（tips：實(shí)際使用中，m的值會超過100，此時即便是千萬級的數(shù)據(jù)量，仍然可以保證在3-4次IO內(nèi)就找到數(shù)據(jù)）

2.和B樹相比文章來源地址http://www.zghlxwxcb.cn/news/detail-571862.html

• B+樹的磁盤IO效率更高。B+樹的數(shù)據(jù)只會存放在葉子結(jié)點(diǎn)（非葉子節(jié)點(diǎn)只存索引信息），而B樹在每個節(jié)點(diǎn)上都要存放數(shù)據(jù)，所以在相同的空間內(nèi)，B+樹可以存放更多地索引信息，IO效率更高（單次IO獲得的索引信息量更大）
• B+樹范圍查找效率更高，B樹進(jìn)行范圍查找需要進(jìn)行樹中序遍歷，而B+樹的葉子結(jié)點(diǎn)使用了雙向鏈表連接起來，范圍查找效率更高。

到了這里，關(guān)于MySQL為什么采用B+樹作為索引底層數(shù)據(jù)結(jié)構(gòu)？的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！