跳轉到

為什麼 MySQL 採用 B+ 樹來實現索引？

要解釋這個問題，其實不單單要從資料結構的角度出發，還要考慮磁盤 I/O 操作次數，因為 MySQL 的資料是存儲在磁盤中的。

怎樣的索引的資料結構是好的？

由於資料庫的索引是保存到磁盤上的，因此當我們通過索引查找某行資料的時候，就需要先從磁盤讀取索引到內存，再通過索引從磁盤中找到某行資料，然後讀入到內存，也就是說查詢過程中會發生多次磁盤 I/O，而磁盤 I/O 次數越多，所消耗的時間也就越大。

所以，我們希望索引的資料結構能在盡可能少的磁盤的 I/O 操作中完成查詢工作，因為磁盤 I/O 操作越少，所消耗的時間也就越小。

另外，MySQL 是支持範圍查找的，所以索引的資料結構不僅要能高效地查詢某一個記錄，而且也要能高效地執行範圍查找。

所以，要設計一個適合 MySQL 索引的資料結構，至少滿足以下要求：

  • 能在盡可能少的磁盤的 I/O 操作中完成查詢工作
  • 要能高效地查詢某一個記錄，也要能高效地執行範圍查找

分析完要求後，我們針對一些資料結構分析一下。

二元搜尋樹

當每次插入的元素都是樹中最大的元素，二元搜尋樹就會變成右傾樹，查找資料的時間複雜度變成了 O(n)。

自平衡二元樹

不管是 AVL 樹還是紅黑樹，都會隨著插入的元素增多，而導致樹的高度變高，這就意味著磁盤 I/O 操作次數多，會影響整體資料查詢的效率。

B 樹

為了降低樹的高度，後面就出來了 B 樹，它不再限制一個節點就只能有 2 個子節點，而是允許 M 個子節點(M > 2)，從而降低樹的高度。

B+ 樹

B+ 樹與 B 樹差異的點，主要是以下這幾點：

  • 葉子節點（最底部的節點）才會存放實際資料（索引+記錄），非葉子節點只會存放索引
  • 所有索引都會在葉子節點出現，葉子節點之間構成一個有序鍊錶
  • 非葉子節點的索引也會同時存在在子節點中，並且是在子節點中所有索引的最大（或最小）
  • 非葉子節點中有多少個子節點，就有多少個索引

B+ 樹的非葉子節點不存放實際的記錄資料，僅存放索引，因此資料量相同的情況下，相比既存索引又存記錄的 B 樹，B+ 樹的非葉子節點可以存放更多的索引，因此 B+ 樹可以比 B 樹更「矮胖」，查詢底層節點的磁盤 I/O 次數會更少。

B+ 樹所有葉子節點間有一個鍊錶進行連接，這種設計對範圍查找非常有幫助。