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

• 每個結點可以存儲多個關鍵字，且每個結點可以有多于兩個的孩子數；

• 所有葉子結點都位于同一層次；

• 有分支結點中的關鍵字會在葉子結點中再次列出，也就是說葉子結點中包含全部關鍵字的信息；

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

• 葉子結點之間依關鍵字的大小自小而大鏈接。

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

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

• 高扇出性：

（扇出，是指上級模塊直接調用的下級模塊的數量）

對于一棵3層的1000階B+樹（結點最大的孩子數目稱為B+樹的階），可以存儲1000的3次方個值，也就是10億個值，這已經可以滿足生產環境中大多數InnoDB表的存儲需求。

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

• 范圍查詢：

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

1. 聚集索引

如下圖所示，即是聚集索引對應的B+樹。其中數字代表每行數據的主鍵值，而葉子結點中的“ROW8”等代表具體的行數據。

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

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

2. 二級索引

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

如圖中所示，二級索引的非葉子結點中僅包含二級索引所在字段的值和指向葉子結點的指針，而葉子結點中包含二級索引值、主鍵值以及指向上一個葉子結點與下一個葉子結點的指針。正因為葉子結點中不包含整行數據，當需要通過二級索引查詢整行數據時，需要通過在二級索引中查詢到的主鍵值，回到聚集索引中再查詢一次，這個過程就被稱為“回表”。

1. 為什么必須設置主鍵？

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

另外可以發現，當主鍵值的長度越小，輔助索引占用的空間也會越小，這是因為輔助索引中并不存儲整行的數據，而是只存儲該行數據的主鍵值。所以一般情況下都會使用自增主鍵。

2. 為什么創建索引耗時久？

因為創建輔助索引時就是憑空生成一棵B+樹，還要根據索引值重新組織數據的排列順序；當創建主鍵索引時，則相當于重新構建聚集索引所在的B+樹。也因為創建索引的成本很高，所以最好在建表的時候就規劃好索引。

3. 當表中索引特別多時，為什么Insert語句會執行比較慢？

因為數據不僅會插入聚集索引所在的B+樹，還會在該表其余所有索引所在B+樹上插入數據（B+樹為了保持平衡，插入操作可能涉及到葉子結點的旋轉、拆分等操作）。在生產環境中，DBA一般都會制定開發規范，例如單張表上創建的索引數不得超過5個。

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

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

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

END

更多精彩干貨分享

點擊下方名片關注

IT那活兒