B+樹是由B樹演化而來，不同于B樹適合在內(nèi)存中遍歷訪問，B+樹十分適合于在磁盤中存儲與讀取。從嚴(yán)格意義上講，B+樹已不滿足“樹”的定義。B+樹的定義這里不再詳細(xì)介紹，這里只介紹B+樹的幾個重要特點(diǎn)。如下圖所示，即是一棵B+樹。

• 每個結(jié)點(diǎn)可以存儲多個關(guān)鍵字，且每個結(jié)點(diǎn)可以有多于兩個的孩子數(shù)；

• 所有葉子結(jié)點(diǎn)都位于同一層次；

• 有分支結(jié)點(diǎn)中的關(guān)鍵字會在葉子結(jié)點(diǎn)中再次列出，也就是說葉子結(jié)點(diǎn)中包含全部關(guān)鍵字的信息；

• 葉子結(jié)點(diǎn)之間通過雙向鏈表鏈接，即每個葉子結(jié)點(diǎn)都有指向上一個和下一個葉子結(jié)點(diǎn)的指針；

• 葉子結(jié)點(diǎn)之間依關(guān)鍵字的大小自小而大鏈接。

2. B+樹為何適合于在磁盤中存儲與讀取

B+樹更適合于在磁盤中存儲與讀取，主要體現(xiàn)在其具有高扇出性和范圍查詢的高效率上。

• 高扇出性：

（扇出，是指上級模塊直接調(diào)用的下級模塊的數(shù)量）

對于一棵3層的1000階B+樹（結(jié)點(diǎn)最大的孩子數(shù)目稱為B+樹的階），可以存儲1000的3次方個值，也就是10億個值，這已經(jīng)可以滿足生產(chǎn)環(huán)境中大多數(shù)InnoDB表的存儲需求。

高扇出性帶來的好處就是查詢效率的提升，比如3層的B+樹，查詢某個關(guān)鍵字只需要3次IO，再考慮到一般情況下，根結(jié)點(diǎn)總會緩存在內(nèi)存中，所以只需要2次IO即可。當(dāng)前一般的機(jī)械硬盤每秒可以做100次IO，所以本次查詢花費(fèi)的時(shí)間僅有0.02秒。

• 范圍查詢：

傳統(tǒng)的二叉樹需要通過前序遍歷或其他遍歷方法來查詢所有結(jié)點(diǎn)中的關(guān)鍵字，而不同于二叉樹，B+樹所有的關(guān)鍵字都按照大小順序保存在葉子結(jié)點(diǎn)中，且通過雙向鏈表鏈接。因此針對范圍查詢，只需要從第一個匹配的關(guān)鍵字，通過鏈表繼續(xù)向下匹配即可。

1. 聚集索引

如下圖所示，即是聚集索引對應(yīng)的B+樹。其中數(shù)字代表每行數(shù)據(jù)的主鍵值，而葉子結(jié)點(diǎn)中的“ROW8”等代表具體的行數(shù)據(jù)。

如圖中所示，非葉子結(jié)點(diǎn)中存放的只有主鍵值以及指向葉子結(jié)點(diǎn)的指針，而葉子結(jié)點(diǎn)中存放的是主鍵值、行數(shù)據(jù)（包含所有字段的值，此處不考慮行溢出數(shù)據(jù)）和指向上一個葉子結(jié)點(diǎn)與下一個葉子結(jié)點(diǎn)的指針。

葉子結(jié)點(diǎn)對應(yīng)著數(shù)據(jù)庫概念中的數(shù)據(jù)頁，在InnoDB存儲引擎中，每個數(shù)據(jù)頁大小默認(rèn)為16KB（innodb_page_size）。如圖中所示，每個數(shù)據(jù)頁中包含多行數(shù)據(jù)，且按照主鍵的大小順序排列，也就是說，InnoDB表是天然排過序的。

2. 二級索引

如下圖所示，即是某個二級索引（輔助索引）對應(yīng)的B+樹。其中字母代表每行數(shù)據(jù)中的輔助索引值（非主鍵值），其中數(shù)字代表每行數(shù)據(jù)中的主鍵值。

如圖中所示，二級索引的非葉子結(jié)點(diǎn)中僅包含二級索引所在字段的值和指向葉子結(jié)點(diǎn)的指針，而葉子結(jié)點(diǎn)中包含二級索引值、主鍵值以及指向上一個葉子結(jié)點(diǎn)與下一個葉子結(jié)點(diǎn)的指針。正因?yàn)槿~子結(jié)點(diǎn)中不包含整行數(shù)據(jù)，當(dāng)需要通過二級索引查詢整行數(shù)據(jù)時(shí)，需要通過在二級索引中查詢到的主鍵值，回到聚集索引中再查詢一次，這個過程就被稱為“回表”。

1. 為什么必須設(shè)置主鍵？

InnoDB表是索引組織表，是通過聚集索引組織數(shù)據(jù)的，如果建表時(shí)定義了主鍵，InnoDB引擎就會選擇主鍵作為聚集索引，如果沒有定義主鍵，InnoDB引擎就會選擇第一個非空（不包含NULL）唯一索引作為聚集索引。如果以上條件都不滿足，InnoDB引擎會選擇內(nèi)置6字節(jié)的ROWID作為隱含的聚集索引。

另外可以發(fā)現(xiàn)，當(dāng)主鍵值的長度越小，輔助索引占用的空間也會越小，這是因?yàn)檩o助索引中并不存儲整行的數(shù)據(jù)，而是只存儲該行數(shù)據(jù)的主鍵值。所以一般情況下都會使用自增主鍵。

2. 為什么創(chuàng)建索引耗時(shí)久？

因?yàn)閯?chuàng)建輔助索引時(shí)就是憑空生成一棵B+樹，還要根據(jù)索引值重新組織數(shù)據(jù)的排列順序；當(dāng)創(chuàng)建主鍵索引時(shí)，則相當(dāng)于重新構(gòu)建聚集索引所在的B+樹。也因?yàn)閯?chuàng)建索引的成本很高，所以最好在建表的時(shí)候就規(guī)劃好索引。

3. 當(dāng)表中索引特別多時(shí)，為什么Insert語句會執(zhí)行比較慢？

因?yàn)閿?shù)據(jù)不僅會插入聚集索引所在的B+樹，還會在該表其余所有索引所在B+樹上插入數(shù)據(jù)（B+樹為了保持平衡，插入操作可能涉及到葉子結(jié)點(diǎn)的旋轉(zhuǎn)、拆分等操作）。在生產(chǎn)環(huán)境中，DBA一般都會制定開發(fā)規(guī)范，例如單張表上創(chuàng)建的索引數(shù)不得超過5個。

4. 為什么覆蓋索引效率會比較高？

前文中介紹了“回表”的概念，而“覆蓋索引”效率高就體現(xiàn)在其避免了“回表”的操作。“覆蓋索引”指從輔助索引中即可查到指定的字段，也可簡單理解為某個輔助索引中包含了所有待查詢的字段。輔助索引至少包含了兩個字段的值，輔助索引值以及其所在行的主鍵值，而聯(lián)合索引中包含的字段值會更多。

另外由于輔助索引中并不包含整行的數(shù)據(jù)，所以其大小也要遠(yuǎn)小于聚集索引，因此可以減少大量的IO操作。在查詢時(shí)巧用覆蓋索引，可以讓查詢更加高效。

END

更多精彩干貨分享

點(diǎn)擊下方名片關(guān)注

IT那活兒