MySQL索引之B-樹與B+樹

本文隻是個人閱讀筆記，原文建議詳細閱讀：什麼是B-樹 什麼是B+樹

我們知道MySQL中索引最常用的資料結構就是

Hash

和

B+Tree

,而其中的B+樹更是大多數 MySQL 存儲引擎的預設索引類型。

• 那究竟什麼是B+樹？什麼又是B樹？它們之間有什麼關系嗎？

B樹/B-樹

1、哈希表、二叉查找樹、B樹的比較

要弄清楚B+樹，就得先知道B-樹（B-樹就是B樹），首先MySQL索引之是以要使用

樹

作為資料結構進行存儲是因為它

查詢效率高，且可以保持有序

，解決

hash

結構

無序

隻能用作等值查詢場景的缺陷。

• 那為什麼不使用二叉查找樹？

我們知道二叉查找樹的查找插入的時間複雜度都是O(logN)，之是以沒有使用二叉查找樹是考慮到了磁盤IO的問題：

索引是存儲在磁盤上的，當資料量很大的時候，整一棵二叉查找樹的高度是很高的。而我們利用索引進行查詢時并不會将整個索引加載到記憶體，而是按頁讀取，将索引逐頁加載到記憶體，其中每個節點代表了一個頁。假設一個二叉查找樹的樹高為N，意味着我們查找一個節點最差情況要進行讀取N次磁盤，而讀取一次磁盤耗費的時間通常需要幾ms，這是非常耗時的，是以我們希望樹高可以盡可能的小，其中的辦法就是使得一個節點的子節點不止隻有2，而是可以有更多的子節點，即是“N叉樹”，而B樹正是符合這個要求的。

• B樹

  B樹是一種多路平衡的查找樹，它的每個節點最多可以包含m個孩子，m稱為B樹的階，而m的大小取決于磁盤頁的大小。

  一個m階的B樹特點如下：

  1. 根結點至少有兩個子女
  2. 每個中間節點（非葉子節點&非根節點）都包含k-1個元素和k個孩子，其中 m/2 <= k <= m
  3. 每一個葉子節點都包含k-1個元素，其中 m/2 <= k <= m
  4. 所有的葉子結點都位于同一層
  5. 每個節點中的元素從小到大排列，節點當中k-1個元素正好是k個孩子包含的元素的

     值域分劃

例如下面3階的B樹：

其中B-樹的查找、插入節點都是遵循這些特點進行操作的

• B-樹的查找（例如查找5）：

  

  

  

  

  

  

• B-樹的插入比較複雜，不展開了解。

B+樹

B+樹是基于B-樹的一種變體，有着比B-樹更高的查詢性能。

一個m階的B+樹具有如下幾個特征：

1. 有k個子樹的中間節點包含有k個元素（B樹中是k-1個元素），每個元素不儲存資料，隻用來索引，所有資料都儲存在葉子節點。
2. 所有的葉子結點中包含了全部元素的資訊，及指向含這些元素記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序連結。
3. 所有的中間節點元素都同時存在于子節點，在子節點元素中是最大（或最小）元素。

如下3階的B+樹：

因為B+樹的好處展現在查詢性能上，現在來看看它的單行查詢和範圍查詢：

• 單行查詢（例如查詢3）：

  

  

  

• B-樹和B+樹中的衛星資料：

衛星資料是值索引元素所指向的資料記錄，比如資料庫中的某一行。在B-樹中，所有節點都帶有衛星資料。而在B+樹中隻有葉子節點帶有衛星資料，其他節點僅是索引，沒有關聯資料。

注：在資料庫的聚集索引中，葉子節點直接包含衛星資料。在非聚集索引中，葉子節點帶有指向衛星資料的指針。

是以單行查詢中，B+樹與B-樹有兩點不同：

1. B+樹中間節點沒有衛星資料，同樣大小的磁盤頁可以容納更多節點元素。意味着B+樹高會比B樹更小，查詢時IO次數更少。
2. B+樹的查詢最終一定會查詢到葉子節點，而B-樹的查詢可能止于葉子節點也可能止于非葉子節點。是以B+樹會更加穩定。

• 範圍查詢（例如查詢範圍3-11）：

  

  

  

  通過圖可以知道，通過B+樹葉子節點的連結清單指針且它的有序性可以快速找到。

B+樹相比B-樹的優勢

1. 單一節點存儲更多的元素，使得查詢的IO次數更少。
2. 所有查詢都要查找到葉子節點，查詢性能穩定。
3. 所有葉子節點形成有序連結清單，便于範圍查詢。