搞懂這個(gè)問(wèn)題之前，我們首先來(lái)看一下MySQL表的存儲(chǔ)結(jié)構(gòu)，再分別對(duì)比二叉樹(shù)、多叉樹(shù)、B樹(shù)和B+樹(shù)的區(qū)別就都懂了。

MySQL的存儲(chǔ)結(jié)構(gòu)

表存儲(chǔ)結(jié)構(gòu)

單位：表>段>區(qū)>頁(yè)>行

在數(shù)據(jù)庫(kù)中， 不論讀一行，還是讀多行，都是將這些行所在的頁(yè)進(jìn)行加載。也就是說(shuō)存儲(chǔ)空間的基本單位是頁(yè)。
一個(gè)頁(yè)就是一棵樹(shù)B+樹(shù)的節(jié)點(diǎn)，數(shù)據(jù)庫(kù)I/O操作的最小單位是頁(yè)，與數(shù)據(jù)庫(kù)相關(guān)的內(nèi)容都會(huì)存儲(chǔ)在頁(yè)的結(jié)構(gòu)里。

B+樹(shù)索引結(jié)構(gòu)

1. 在一棵B+樹(shù)中，每個(gè)節(jié)點(diǎn)為都是一個(gè)頁(yè)，每次新建節(jié)點(diǎn)的時(shí)候，就會(huì)申請(qǐng)一個(gè)頁(yè)空間
2. 同一層的節(jié)點(diǎn)為之間，通過(guò)頁(yè)的結(jié)構(gòu)構(gòu)成了一個(gè)雙向鏈表
3. 非葉子節(jié)點(diǎn)為，包括了多個(gè)索引行，每個(gè)索引行里存儲(chǔ)索引鍵和指向下一層頁(yè)面的指針
4. 葉子節(jié)點(diǎn)為，存儲(chǔ)了關(guān)鍵字和行記錄，在節(jié)點(diǎn)內(nèi)部（也就是頁(yè)結(jié)構(gòu)的內(nèi)部）記錄之間是一個(gè)單向的鏈表
   

B+樹(shù)頁(yè)節(jié)點(diǎn)結(jié)構(gòu)

有以下幾個(gè)特點(diǎn)

1. 將所有的記錄分成幾個(gè)組， 每組會(huì)存儲(chǔ)多條記錄，
2. 頁(yè)目錄存儲(chǔ)的是槽（slot），槽相當(dāng)于分組記錄的索引，每個(gè)槽指針指向了不同組的最后一個(gè)記錄
3. 我們通過(guò)槽定位到組，再查看組中的記錄
   

頁(yè)的主要作用是存儲(chǔ)記錄，在頁(yè)中記錄以單鏈表的形式進(jìn)行存儲(chǔ)。
單鏈表優(yōu)點(diǎn)是插入、刪除方便，缺點(diǎn)是檢索效率不高，最壞的情況要遍歷鏈表所有的節(jié)點(diǎn)。因此頁(yè)目錄中提供了二分查找的方式，來(lái)提高記錄的檢索效率。

B+樹(shù)的檢索過(guò)程

我們?cè)賮?lái)看下B+樹(shù)的檢索過(guò)程

1. 從B+樹(shù)的根開(kāi)始，逐層找到葉子節(jié)點(diǎn)。
2. 找到葉子節(jié)點(diǎn)為對(duì)應(yīng)的數(shù)據(jù)頁(yè)，將數(shù)據(jù)葉加載到內(nèi)存中，通過(guò)頁(yè)目錄的槽采用二分查找的方式先找到一個(gè)粗略的記錄分組。
3. 在分組中通過(guò)鏈表遍歷的方式進(jìn)行記錄的查找。

為什么要用B+樹(shù)索引

數(shù)據(jù)庫(kù)訪(fǎng)問(wèn)數(shù)據(jù)要通過(guò)頁(yè)，一個(gè)頁(yè)就是一個(gè)B+樹(shù)節(jié)點(diǎn)，訪(fǎng)問(wèn)一個(gè)節(jié)點(diǎn)相當(dāng)于一次I/O操作，所以越快能找到節(jié)點(diǎn)，查找性能越好。
B+樹(shù)的特點(diǎn)就是夠矮夠胖，能有效地減少訪(fǎng)問(wèn)節(jié)點(diǎn)次數(shù)從而提高性能。

下面，我們來(lái)對(duì)比一個(gè)二叉樹(shù)、多叉樹(shù)、B樹(shù)和B+樹(shù)。

二叉樹(shù)

二叉樹(shù)是一種二分查找樹(shù)，有很好的查找性能，相當(dāng)于二分查找。
但是當(dāng)N比較大的時(shí)候，樹(shù)的深度比較高。數(shù)據(jù)查詢(xún)的時(shí)間主要依賴(lài)于磁盤(pán)IO的次數(shù)，二叉樹(shù)深度越大，查找的次數(shù)越多，性能越差。
最壞的情況是退化成了鏈表，如下圖

為了讓二叉樹(shù)不至于退化成鏈表，人們發(fā)明了AVL樹(shù)（平衡二叉搜索樹(shù)）：任何結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)高度最多相差1

多叉樹(shù)

多叉樹(shù)就是節(jié)點(diǎn)可以是M個(gè)，能有效地減少高度，高度變小后，節(jié)點(diǎn)變少I(mǎi)/O自然少，性能比二叉樹(shù)好了

B樹(shù)

B樹(shù)簡(jiǎn)單地說(shuō)就是多叉樹(shù)，每個(gè)葉子會(huì)存儲(chǔ)數(shù)據(jù)，和指向下一個(gè)節(jié)點(diǎn)的指針。

例如要查找9，步驟如下

1. 我們與根節(jié)點(diǎn)的關(guān)鍵字 (17，35）進(jìn)行比較，9 小于 17 那么得到指針 P1；
2. 按照指針 P1 找到磁盤(pán)塊 2，關(guān)鍵字為（8，12），因?yàn)?9 在 8 和 12 之間，所以我們得到指針 P2；
3. 按照指針 P2 找到磁盤(pán)塊 6，關(guān)鍵字為（9，10），然后我們找到了關(guān)鍵字 9。
   

B+樹(shù)

B+樹(shù)是B樹(shù)的改進(jìn)，簡(jiǎn)單地說(shuō)是：只有葉子節(jié)點(diǎn)才存數(shù)據(jù)，非葉子節(jié)點(diǎn)是存儲(chǔ)的指針；所有葉子節(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表

B+樹(shù)的內(nèi)部節(jié)點(diǎn)并沒(méi)有指向關(guān)鍵字具體信息的指針，因此其內(nèi)部節(jié)點(diǎn)相對(duì)B樹(shù)更小，如果把所有同一內(nèi)部節(jié)點(diǎn)的關(guān)鍵字存放在同一盤(pán)塊中，那么盤(pán)塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多，一次性讀入內(nèi)存的需要查找的關(guān)鍵字也就越多，相對(duì)IO讀寫(xiě)次數(shù)就降低了

例如要查找關(guān)鍵字16，步驟如下

1. 與根節(jié)點(diǎn)的關(guān)鍵字 (1，18，35) 進(jìn)行比較，16 在 1 和 18 之間，得到指針 P1（指向磁盤(pán)塊 2）
2. 找到磁盤(pán)塊 2，關(guān)鍵字為（1，8，14），因?yàn)?16 大于 14，所以得到指針 P3（指向磁盤(pán)塊 7）
3. 找到磁盤(pán)塊 7，關(guān)鍵字為（14，16，17），然后我們找到了關(guān)鍵字 16，所以可以找到關(guān)鍵字 16 所對(duì)應(yīng)的數(shù)據(jù)。

B+樹(shù)與B樹(shù)的不同：

1. B+樹(shù)非葉子節(jié)點(diǎn)不存在數(shù)據(jù)只存索引，B樹(shù)非葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)
2. B+樹(shù)查詢(xún)效率更高。B+樹(shù)使用雙向鏈表串連所有葉子節(jié)點(diǎn)，區(qū)間查詢(xún)效率更高（因?yàn)樗袛?shù)據(jù)都在B+樹(shù)的葉子節(jié)點(diǎn)，掃描數(shù)據(jù)庫(kù) 只需掃一遍葉子結(jié)點(diǎn)就行了），但是B樹(shù)則需要通過(guò)中序遍歷才能完成查詢(xún)范圍的查找。
3. B+樹(shù)查詢(xún)效率更穩(wěn)定。B+樹(shù)每次都必須查詢(xún)到葉子節(jié)點(diǎn)才能找到數(shù)據(jù)，而B(niǎo)樹(shù)查詢(xún)的數(shù)據(jù)可能不在葉子節(jié)點(diǎn)，也可能在，這樣就會(huì)造成查詢(xún)的效率的不穩(wěn)定
4. B+樹(shù)的磁盤(pán)讀寫(xiě)代價(jià)更小。B+樹(shù)的內(nèi)部節(jié)點(diǎn)并沒(méi)有指向關(guān)鍵字具體信息的指針，因此其內(nèi)部節(jié)點(diǎn)相對(duì)B樹(shù)更小，通常B+樹(shù)矮更胖，高度小查詢(xún)產(chǎn)生的I/O更少。
   

這就是MySQL使用B+樹(shù)的原因，就是這么簡(jiǎn)單！

以上就是mysql 使用B+樹(shù)索引有哪些優(yōu)勢(shì)的詳細(xì)內(nèi)容，更多關(guān)于MySQL 使用B+樹(shù)索引的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！