你可能已經(jīng)知道 B+ 樹被用于 MySQL 的Innodb引擎的索引底層實現(xiàn)，那么，為什么是 B+ 樹呢？本文由淺及深，探索數(shù)據(jù)庫索引底層實現(xiàn)。

關(guān)于常見分布式組件高可用設(shè)計原理的理解和思考

---

1. 由一個例子總結(jié)索引的特點

加索引是數(shù)據(jù)庫加速查詢的一種方式，那么為什么用索引可以加快查詢呢？講到索引，其實我們經(jīng)常會聽到一個圖書館的例子，圖書館里的書目繁雜，我們?nèi)绾螐娜舾杀緯锩嬲业揭槐疚覀兿胍臅?#xff1f;我們根據(jù)圖書館系統(tǒng)檢索，可以找到某本書對應(yīng)的圖書編號。在基于書籍按照一定規(guī)則排列的前提下，我們可以根據(jù)圖書編號找到這本書。

例如，假設(shè)圖書編號根據(jù)：

• 第幾個書架 - 書架上第幾個格子（第幾層） - 從左到右數(shù)第幾個位置
• 這樣的規(guī)則編排，我們就可以輕松的獲取到我們想要的書籍。

你也許發(fā)現(xiàn)了，這個例子中，藏著兩個信息：

• 按照一定的規(guī)則排列
• 有序

按照一定的規(guī)則，建立一定的映射關(guān)系，這讓你聯(lián)想到了什么？沒錯，就是哈希表。

2. 基于哈希表實現(xiàn)的哈希索引

探討哈希索引相關(guān)特性。

在 MySQL 的 InnoDB 引擎中，自適應(yīng)哈希索引就是用哈希表實現(xiàn)的。哈希索引是數(shù)據(jù)庫自身創(chuàng)建并使用的，DBA 本身不能對其進行干預(yù)，但是可以通過參數(shù)來禁止或者啟用此特性。

顯然用哈希表實現(xiàn)索引的好處是非常明顯的，查找單個指定數(shù)據(jù)只需要O(1)的時間復(fù)雜度。列入如下sql語句：

select id from tablename where id = 1;

但是對于這種查找指定范圍的 sql 語句，哈希索引就無能為力了。

select id from tablename where id BETWEEN 20 AND 23;

原因是哈希這種數(shù)據(jù)結(jié)構(gòu)，本身是無序的，因此針對數(shù)據(jù)排序難以獲取好的效果

到這里我們遇到了一個問題，就是哈希表雖然從查找效率上滿足了我們查找單個數(shù)據(jù)的要求，但是顯然，當(dāng)遇到范圍查詢時，由于哈希表本身的無序性，不利于指定范圍查找。因此我們需要針對這種類型的查詢獲取更加友好的數(shù)據(jù)結(jié)構(gòu)方式，以獲取更好的查詢性能。

也就是說，我們的需求增加了，我們希望數(shù)據(jù)的組織方式，既要有一定規(guī)則，又要有序。在引出這種數(shù)據(jù)結(jié)構(gòu)之前，我們首先來看一種查找方式：二分查找。

3. 高效的查找方式：二分查找

二分查找的核心思想是給定一個 有序 的數(shù)組，在查找過程中采用跳躍式的方式查找，即先以有序數(shù)列的中點位置為比較對象，如果要查找的元素小于中點元素，則將待查序列縮小為左半部分，否則為右半部分。通過每次比較，將查找區(qū)間減少一半，直到找到所需元素。

比如要從以下序列中查找到數(shù)字 4

[1,3,4,5,6,7,8]

需要經(jīng)過下面的查找步驟：

• 取中心位置對應(yīng)元素，顯然 5 大于 4，在左邊區(qū)間 [1,3,4] 進行查找
• 繼續(xù)取中心位置對應(yīng)元素 3，顯然 3 大于 4,在右邊區(qū)間 [4] 進行查找
• 4 等于 4，所以我們查找成功。

可以看到二分查找的效率是 O(log n)。

由于有序數(shù)組自身的有序性，所以范圍查詢依然可以通過二分查找的方式查找區(qū)間的邊界來實現(xiàn)。
這樣看來，如果單從查詢效率上來說，有序的數(shù)組是一種很好的選擇。但是顯然有序數(shù)組對于插入和刪除并不友好，假設(shè)我們要插入元素或者刪除元素，都需要把部分元素全部向后或者向前移動，最糟糕的時間復(fù)雜度是 。

有沒有這樣一種數(shù)據(jù)結(jié)構(gòu)，既有一定順序，又方便插入和刪除呢？事實上，基于二分查找的思想，誕生了這樣一種數(shù)據(jù)結(jié)構(gòu)：二分查找樹。

4. 基于二分查找思想的二叉查找樹

二叉查找樹（Binary Search Tree）即BST樹是這樣的一種數(shù)據(jù)結(jié)構(gòu),如下圖：

在二叉搜索樹中：

• 若任意結(jié)點的左子樹不空，則左子樹上所有結(jié)點的值均不大于它的根結(jié)點的值。
• 若任意結(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均不小于它的根結(jié)點的值。
• 任意結(jié)點的左、右子樹也分別為二叉搜索樹。

這樣的結(jié)構(gòu)非常適合用二分查找的思維查找元素。

比如我們需要查找鍵值為8的記錄：

• 先從根找起，找到 6；
• 顯然 8>6，所以接著找到 6 的右子樹，找到 7；
• 顯然 8>7, 所以找 7 的右子樹，找到了 8，查找結(jié)束。

這樣一棵子樹高度差不大于 1 的二叉查找樹的查找效率接近與O(logn);

但是當(dāng)二叉樹的構(gòu)造變成這樣時, 此時我們再查找 8 時,查找效率就淪為接近順序遍歷查找的效率。

顯然這不是我們想要的，二叉查找樹也需要 balance，以控制二叉樹的層高和規(guī)格配置

5. 升級版的BST樹：AVL 樹

我們對二叉查找樹做個限制，限制必須滿足任何節(jié)點的兩個子樹的最大差為 1，也是AVL 樹的定義，這樣我們的查找效率就有了一定的保障。AVL 樹 是一種自平衡二叉查找樹(self-balancing binary search tree)。

當(dāng)然，維護AVL 樹也是需要一定開銷的，即當(dāng)樹插入/更新/刪除新的數(shù)據(jù)時假設(shè)破壞了樹的平衡性，那么需要通過左旋和右旋來維護樹的平衡。當(dāng)數(shù)據(jù)量很多時，同樣也會出現(xiàn)二叉樹過高的情況。

我們知道AVL 樹的查找效率為 O(log n)，也就是說，當(dāng)樹過高時，查找效率會下降。

另外由于我們的索引文件并不小，所以是存儲在磁盤上的。文件系統(tǒng)需要從磁盤讀取數(shù)據(jù)時，一般以頁為單位進行讀取，假設(shè)一個頁內(nèi)的數(shù)據(jù)過少，那么操作系統(tǒng)就需要讀取更多的頁，涉及磁盤隨機 I/O 訪問的次數(shù)就更多。

將數(shù)據(jù)從磁盤讀入內(nèi)存涉及隨機 I/O 的訪問，是數(shù)據(jù)庫里面成本最高的操作之一。因而這種樹高會隨數(shù)據(jù)量增多急劇增加，每次更新數(shù)據(jù)又需要通過左旋和右旋維護平衡的二叉樹，不太適合用于存儲在磁盤上的索引文件。

因此我們應(yīng)該盡可能的減少文件系統(tǒng)的隨機訪問，解決的思路應(yīng)該是

• 一個文件系統(tǒng)頁應(yīng)該盡可能的保存多的數(shù)據(jù)，以減少頁的數(shù)量訪問，提升效率
• 減少樹的層高

6. 更加符合磁盤特征的B樹

前面我們看到，雖然AVL樹既有鏈表的快速插入與刪除操作的特點，又有數(shù)組快速查找的優(yōu)勢，但是這并不是最符合磁盤讀寫特征的數(shù)據(jù)結(jié)構(gòu)。

也就是說，我們要找到這樣一種數(shù)據(jù)結(jié)構(gòu)，能夠有效的控制樹高，那么我們把二叉樹變成m叉樹，也就是下圖的這種數(shù)據(jù)結(jié)構(gòu):B 樹。

B樹是一種這樣的數(shù)據(jù)結(jié)構(gòu)：

根結(jié)點至少有兩個子結(jié)點;

• 每個中間節(jié)點都包含 k-1 個元素和k個子結(jié)點，其中 m/2 <= k <= m;
• 每一個葉子結(jié)點都包含 k-1 個元素，其中 m/2 <= k <= m;
• 所有的葉子結(jié)點都位于同一層;
• 每個結(jié)點中關(guān)鍵字從小到大排列，并且當(dāng)該結(jié)點的孩子是非葉子結(jié)點時，該 k-1 個元素正好是 k 個子結(jié)點包含的元素的值域的分劃。

可以看到，B樹在保留二叉樹預(yù)劃分范圍從而提升查詢效率的思想的前提下，做了以下優(yōu)化：

• 二叉樹變成 m 叉樹，這個 m 的大小可以根據(jù)單個頁的大小做對應(yīng)調(diào)整，從而使得一個頁可以存儲更多的數(shù)據(jù)，從磁盤中讀取一個頁可以讀到的數(shù)據(jù)就更多，隨機 IO 次數(shù)變少，大大提升效率。
• 但是我們看到，我們只能通過中序遍歷查詢?nèi)?#xff0c;當(dāng)進行范圍查詢時，可能會需要中序回溯。如果出現(xiàn)查詢回溯，就會導(dǎo)致查詢的路徑層高變高，隨機IO次數(shù)進一步提升。

因此需要針對B樹進一步調(diào)整

7. 不斷優(yōu)化的B樹：B+ 樹

基于以上的缺陷，又誕生了一種新的優(yōu)化B樹的樹: B+ 樹

B+樹在B樹的基礎(chǔ)上加了以下優(yōu)化：

• 葉子結(jié)點增加了指針進行連接，即葉子結(jié)點間形成了鏈表；
• 非葉子結(jié)點只存關(guān)鍵字 key，不再存儲數(shù)據(jù)，只在葉子結(jié)點存儲數(shù)據(jù)；

說明：葉子之間用雙向鏈表連接比單向鏈表連接多出的好處是通過鏈表中任一結(jié)點都可以通過往前或者往后遍歷找到鏈表中指定的其他結(jié)點。

這樣做的好處是：

• 范圍查詢時可以通過訪問葉子節(jié)點的鏈表進行有序遍歷，而不再需要中序回溯訪問結(jié)點。
• 非葉子結(jié)點只存儲關(guān)鍵字key，一方面這種結(jié)構(gòu)相當(dāng)于劃分出了更多的范圍，加快了查詢速度，另一方面相當(dāng)于單個索引值大小變小，同一個頁可以存儲更多的關(guān)鍵字，讀取單個頁就可以得到更多的關(guān)鍵字，可檢索的范圍變大了，相對 IO 讀寫次數(shù)就降低了。

8. 疑問和思考

一些總結(jié)

8.1 B+ 樹和 B 樹的區(qū)別？

B 樹非葉子結(jié)點和葉子結(jié)點都存儲數(shù)據(jù),因此查詢數(shù)據(jù)時，時間復(fù)雜度最好為 O(1),最壞為 O(log n)。
B+ 樹只在葉子結(jié)點存儲數(shù)據(jù)，非葉子結(jié)點存儲關(guān)鍵字，且不同非葉子結(jié)點的關(guān)鍵字可能重復(fù)，因此查詢數(shù)據(jù)時，時間復(fù)雜度固定為 O(log n)。

B+ 樹葉子結(jié)點之間用鏈表相互連接，因而只需掃描葉子結(jié)點的鏈表就可以完成一次遍歷操作，B樹只能通過中序遍歷。

為什么 B+ 樹比 B 樹更適合應(yīng)用于數(shù)據(jù)庫索引？
B+ 樹更加適應(yīng)磁盤的特性，相比 B 樹減少了 I/O 讀寫的次數(shù)。由于索引文件很大因此索引文件存儲在磁盤上，B+ 樹的非葉子結(jié)點只存關(guān)鍵字不存數(shù)據(jù)，因而單個頁可以存儲更多的關(guān)鍵字，即一次性讀入內(nèi)存的需要查找的關(guān)鍵字也就越多，磁盤的隨機 I/O 讀取次數(shù)相對就減少了。

B+ 樹的查詢效率相比B樹更加穩(wěn)定，由于數(shù)據(jù)只存在在葉子結(jié)點上，所以查找效率固定為 O(log n)。
B+ 樹葉子結(jié)點之間用鏈表有序連接，所以掃描全部數(shù)據(jù)只需掃描一遍葉子結(jié)點，利于掃庫和范圍查詢；B 樹由于非葉子結(jié)點也存數(shù)據(jù)，所以只能通過中序遍歷按序來掃。

也就是說，對于范圍查詢和有序遍歷而言，B+ 樹的效率更高。

9. 參考文檔

• 暫無