談到索引，大家并不陌生。索引本身是一種數據結構，存在的目的主要是為了縮短數據檢索的時間，最大程度減少磁盤 IO。

任何有數據的場景幾乎都有索引，比如手機通訊錄、文件系統（ext4xfsntfs)、數據庫系統（MySQLOracle）。數據庫系統和文件系統一般都采用 B+ 樹來存儲索引信息，B+ 樹兼顧寫和讀的性能，最極端時檢索復雜度為 O(logN)，其中 N 指的是節點數量，logN 表示對磁盤 IO 掃描的總次數。

MySQL 支持的索引結構有四種：B+ 樹，R 樹，HASH，FULLTEXT。

本篇簡單介紹下 B+ 樹，下一篇講 MySQL 常用的兩種引擎 MyISAM 和 InnoDB 的 B+ 樹索引實現，其余的后面會講到。

一、什么是二叉樹？

再講什么是 B+ 樹之前，先來了看下什么是二叉樹。

樹本身是一種數據存儲結構，因為類似現實生活中的樹而命名。

一個看似沒有修剪過的樹，其實這是一棵二叉樹，每個節點最多有兩個子節點。

樹相關的基礎概念：

拿圖 1 這棵樹舉例說明：

• 根節點：6 為根節點，根節點沒有父節點，有兒子節點，一般叫做 ROOT 節點；
• 兒子節點：8 和 4 是 6 的兒子節點，4 是左兒子，8 是右兒子；
• 父節點：6 是 4 和 8 的父節點，父節點是兒子節點的上層節點；
• 葉子節點：4 和 5 是葉子節點，葉子節點指的是除根節點外沒有兒子的節點；
• 兄弟節點：8 和 4 互為兄弟節點，因為有共同的父親 6。10，9，7 三個節點沒有兄弟，都只有一個兒子；
• 層數：一棵樹的節點層數。圖 1 層數為 6；
• 高度：自下向上遍歷，從葉子節點遍歷到根節點所需要的節點數量。葉子節點 5 到根節點遍歷 7，9，10，8，6，這棵樹的高度為 5；
• 深度：自上而下遍歷，從根節點到葉子節點遍歷所需要的節點數量，同樣，這棵樹的深度也是 5；
• 高度和深度一般以 0 開始計算，當然也有按照從 1 開始計算的；
• 平衡因子：某節點的左子樹與右子樹深度的差值，一般結果為絕對值。
  如果任何一個子樹不存在，按照 0 處理。比如節點 10 的平衡因子就是 3；

圖 1 是一顆非常普通的樹，非常容易退化為一張鏈表。如果把圖 1 換成如下圖， 根節點就變為 4，6 退化為 4 的兒子節點，這棵樹就退化為一張鏈表。

鏈表的查找非常慢，只能按照節點順序查找，每個節點都遍歷一遍，時間復雜度為 O(n)，無法隨機查找。

二、平衡二叉樹（AVL）

那對圖 1 進行下改造，把數據重新節點重新連接下，圖 2 如下：

圖 2 可以看到以下特性：

1. 所有左子樹的節點都小于其對應的父節點（4，5，6）<（7）；（4）<（5）；（8）< （9）；

2. 所有右子樹上的節點都大于其對應的父節點（8，9，10）>（7）；（6）>（5）；（10）>（9）；

3. 每個節點的平衡因子差值絕對值 <=1；

4. 每個節點都符合以上三個特征。

滿足這樣條件的樹叫平衡二叉樹（AVL）樹。

問：那再次查找節點 5，需要遍歷多少次呢？

由于數據是按照順序組織的，那查找起來非?？?#xff0c;從上往下找：7-5，只需要在左子樹上查找，也就是遍歷 2 次就找到了 5。假設要找到葉子節點 10，只需要在右子樹上查找，那也最多需要 3 次，7-9-10。也就說 AVL 樹在查找方面性能很好，最壞的情況是找到一個節點需要消耗的次數也就是樹的層數， 復雜度為 O(logN)

如果節點非常多呢？假設現在有 31 個節點，用 AVL 樹表示如圖 3：

圖 3 是一棵高度為 4 的 AVL 樹，有 5 層共 31 個節點，橙色是 ROOT 節點，藍色是葉子節點。對 AVL 樹的查找來看起來已經很完美了，能不能再優化下？比如，能否把這個節點里存放的 KEY 增加？能否減少樹的總層數？那減少縱深只能從橫向來想辦法，這時候可以考慮用多叉樹。

三、B 樹

B 樹是一種多叉的 AVL 樹。B-Tree 減少了 AVL 數的高度，增加了每個節點的 KEY 數量。

B 樹的特性：（m 為階數：結點的孩子個數最大值）

1. 樹中每個節點最多含有 m 個孩子節點 (m>=2)；

2. 除根節點和葉子結點外，其他節點的孩子數量 >=ceil(m / 2)；

3. 若根節點不是葉子結點，最少有兩個孩子

• 特殊情況：沒有孩子的根結點，即根結點為葉子結點，整棵樹只有一個根節點；

4. 每個非葉子結點中包含有 n 個關鍵字信息：(n，P0，K1，P1，K2，P2，......，Kn，Pn) 其中：

• Ki (i=1...n) 為關鍵字，且關鍵字按順序升序排序 K(i-1)< Ki
• Pi 為指向兒子節點的指針，且指針 P(i-1) 指向的兒子節點里所有關鍵字均小于 Ki，但都大于 K(i-1)
• 關鍵字的個數 n 必須滿足：[ceil(m / 2)-1]<= n <= m-1
• 如果一個結點有 n 個關鍵字，那么該結點有 n+1 個分支。這 n+1 個關鍵字按照遞增順序排列
• 所有葉子結點都出現在同一層，是所有遍歷的終點位置

按照這個要求，把圖 3 簡單變為一棵 B 樹，見圖 4：

圖 4 是一棵 4 階 B 樹，總共有 11 個節點，節點數比圖 3 少了 20 個；層數為 3，比圖 3 少了兩層。實際應用中，每個最小單元不是 KEY，而一般是按照塊（BLOCK）來算。比如磁盤文件系統 EXT4 每塊 4KB；數據庫比如 PostgreSQL 是 8KB，MySQL InnoDB 是 16KB， MySQL NDB 是 32KB 等。

所以再次理清圖 4 的 B 樹，變為圖 5：

圖 5 每個節點的基本單元是一個磁盤塊（BLOCK，默認 4KB），根節點含有一個鍵值，其他節點含有 3 個鍵值，每個磁盤塊包含對應的鍵值與數據。

比如現在要讀取 KEY 為 31 的記錄：先找到根節點磁盤塊（1），讀入內存。（第一次 IO）；關鍵字 31 大于區間（16，），根據指針 P2 找到磁盤塊 3，讀入內存（第二次 IO）；31 大于區間（20，24，28），根據指針 P4 讀取磁盤塊 11（第三次 IO），在磁盤塊 11 中找到 KEY 為 31 的記錄，返回結果。這期間有三次磁盤 IO 的讀取。可以明確看到，B 樹相對于 AVL 樹，減少了樹的節點數與樹的深度，減少了磁盤 IO。

看到這里其實有一個問題，三次 IO，前兩次 IO 其實從磁盤讀取了不必要的數據，因為只用比較 KEY，所以非葉子節點對應的 DATA 完全沒有必要，如果 DATA 很大，那完全是浪費內存資源?？紤]下能否把非葉子節點的 DATA 拿掉？

四、B+ 樹

B+ 樹是對 B 樹的一個小升級。大部分數據庫的索引都是基于 B+ 樹存儲的。MySQL 的 MyISAM 和 InnoDB 引擎的索引都是基于 B+ 樹存儲。

B+ 樹最大的幾個特點：

1. 非葉子節點只保留 KEY，放棄 DATA；

2. KEY 和 DATA一起，在葉子節點，并且保存為一個有序鏈表（正序，反序，或者雙向）；

3. B+ 樹的查找與 B 樹不同，當某個結點的 KEY 與所查的 KEY 相等時，并不停止查找，而是沿著這個 KEY 左邊的指針向下，一直查到該關鍵字所在的葉子結點為止。

那對圖 5 的 B 樹做一個調整，變為以下 B+ 樹，見圖 6：

圖 6 是一棵 6 階 B+ 樹。不同于圖 5，非葉子節點不再包含除了主鍵外的數據，數據全部放在葉子節點，并且所有葉子節點存放在一個單向鏈表里，當然也可以雙向鏈表?？梢钥吹?#xff0c;B+ 樹同時具有平衡多叉樹和鏈表的優點，即可兼顧 B 樹對范圍查找的高效，又可兼顧鏈表隨機寫入的高效， 這也是大部分數據庫都用 B+ 樹來存儲索引的原因。

本篇是為了下一篇介紹 MySQL 的兩種常用引擎：MyISAM 和 InnoDB 索引結構做了一個鋪墊，下期見。

---

關于 MySQL 的技術內容，你們還有什么想知道的嗎？趕緊留言告訴小編吧！

總結

以上是生活随笔為你收集整理的高度为5的3阶b树含有的关键字个数_第15期：索引设计（索引组织方式 B+ 树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。