Table Index

前面介紹完了 Hash Table，在數(shù)據(jù)庫系統(tǒng)中，它可以用于一些 sql 執(zhí)行時的臨時數(shù)據(jù)結(jié)構(gòu)，或者用來存儲一些元數(shù)據(jù)信息，也可以作為表的 Hash 索引，但是對于表索引，在更通用的場景下， B+ 樹是更廣泛的選擇。

表索引（Index）指的是表中數(shù)據(jù)的一些子集，這些子集能夠標(biāo)識表中數(shù)據(jù)的一些特征，以便能夠快速的去查找 table 中的數(shù)據(jù)，并且數(shù)據(jù)庫能夠保證，表中數(shù)據(jù)和表索引數(shù)據(jù)的一致性。

B+ Tree 基本概念

B+ Tree 實際上是一種平衡樹結(jié)構(gòu)，它能夠保證數(shù)據(jù)有序存儲，可以在平均 O(log n) 復(fù)雜度下查詢、插入、刪除數(shù)據(jù)。

它實際上類似二叉平衡樹，但是每個節(jié)點可以擁有不止 2 個子節(jié)點，并且能夠適配數(shù)據(jù)庫需要讀取整塊數(shù)據(jù)的需求，提升數(shù)據(jù)讀寫的效率。

B+ 樹是一個多叉平衡樹，例如 M 個分叉指的是每個 inner node 都有 M 個路徑到子節(jié)點，具有以下基本特征：

• 完全平衡的樹結(jié)構(gòu)，即所有子節(jié)點到根節(jié)點的距離始終保持一致
• 除根節(jié)點外，每個節(jié)點的數(shù)據(jù)量至少大于 M 的一半，即 M/2-1 <= #keys <= M-1
• 每一個具有 k 個 key 的節(jié)點內(nèi)，都有 k+1 個指向子節(jié)點的指針

下圖所示，是一個 B+ Tree 的例子。

最底層的節(jié)點叫做 leaf node 葉子節(jié)點，上層的叫做 inner node，最頂層的 inner node 就是根節(jié)點（root node）。

inner node 中不會存儲實際的數(shù)據(jù)，而是存儲 key 以及指向其子節(jié)點的指針。

葉子節(jié)點之間有指針串聯(lián)，方便進行 scan 操作；每個葉子節(jié)點中存儲了實際的 key/value 數(shù)據(jù)。

葉子節(jié)點的內(nèi)部結(jié)構(gòu)，一般有兩種不同的布局方式，一種是很常見的，存儲一個 page id，并且將索引的 key 和 value 都存放到節(jié)點中，然后一個 page 指向下一個 page。

這樣是將 key/value 保存在了一起，并不利于順序掃描，如果我們只需要掃描 key 的話，那么會有一些額外的消耗。

另一種方式是將 key 和 value 分開，結(jié)構(gòu)大致如下所示：

其中包含了一些元數(shù)據(jù)信息，例如當(dāng)前的層數(shù)，空閑空間等，以及一個有序的 key 列表，并且每一個 key 指向了它自己的 value。

而實際 value 所表示的數(shù)據(jù)，各個系統(tǒng)有不同的實現(xiàn)，大致有兩種：一是存儲一個記錄 id，指向磁盤的 page 中數(shù)據(jù)的實際位置；二是直接就存儲數(shù)據(jù)本身。

B+ Tree 操作

insert

B+ 樹中插入操作大致流程如下：

• 首先從根節(jié)點開始，通過 inner node 的指針，層層往下找到對應(yīng)的葉子節(jié)點 L
• 將數(shù)據(jù)存儲到葉子節(jié)點中
• 如果節(jié)點 L 中還有空閑空間，則操作完成
• 否則，分裂（split）該葉子節(jié)點

重新分布該葉子節(jié)點上的數(shù)據(jù)，以最中間的 key 為界，右邊的數(shù)據(jù)分裂到新的節(jié)點中

分裂的時候，需要將葉子節(jié)點中間的 key 推送到上層父節(jié)點

如果上層父節(jié)點又需要分裂，則重復(fù)執(zhí)行上述過程

delete

delete 操作大致是和 insert 相反的，插入的時候，如果一個節(jié)點上的數(shù)據(jù)滿了，則需要分裂；而刪除時，如果一個節(jié)點中的數(shù)據(jù)少于了 M/2-1，則破壞了 B+ Tree 的定義，這時候需要將節(jié)點進行合并，稱為 merge。

大致過程如下：

• 通過 inner node 節(jié)點找到對應(yīng)的葉子節(jié)點 L
• 在 L 中找到對應(yīng)的數(shù)據(jù)并刪除
• 如果葉子節(jié)點中的數(shù)據(jù)大于等于 M/2-1，則完成
• 否則，需要進行 merge 合并節(jié)點

嘗試重分布，如果鄰近節(jié)點有富余，則從鄰近的節(jié)點中拿一個 key

如果鄰近節(jié)點也沒有多余的數(shù)據(jù)，則嘗試和兄弟節(jié)點合并

這里有一個網(wǎng)站，動態(tài)展示了 B+ 樹的插入、刪除、查找過程，能夠更好幫你理解 B+ 樹。https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

B+ Tree Design

接下來在簡要分析下關(guān)于 B+ Tree 的一些設(shè)計問題。

Node Size

對于 B+ 樹中每個節(jié)點的大小，這其實并不確定，或者說依賴于硬件環(huán)境和數(shù)據(jù)庫類型，sql 查詢類型等因素。

大致來說，存儲介質(zhì)速度越慢，則一個節(jié)點的容量就越大，道理也很簡單。當(dāng)在慢速的介質(zhì)中，例如磁盤，我么肯定希望能夠一次性多讀取一部分?jǐn)?shù)據(jù)到內(nèi)存中，盡量避免多次隨機 IO。在越快速的設(shè)備上，則節(jié)點的容量越小。

可以參考內(nèi)存中的 cache line 和操作系統(tǒng)維護的 page size。MySQL 的 B+ 樹節(jié)點大小一般是 16KB。

Merge Threshold

前面說到了刪除數(shù)據(jù)時可能會觸發(fā) B+ 樹的 merge 節(jié)點操作，但是在實際的實現(xiàn)中，一些數(shù)據(jù)庫系統(tǒng)并不是只要滿足條件就會馬上執(zhí)行，而是累積到一段時間之后，再進行 merge。

因為 merge 是一個很“昂貴”的操作，涉及到磁盤上的數(shù)據(jù)調(diào)整分布，一些系統(tǒng)中會有一些后臺進程，定期去觸發(fā)這個操作。

Variable-Length Keys

前面提到的 B+ Tree 中存儲的都是固定 size 的 key，但是實際環(huán)境中，我們的 key 或者 value 都有可能是不定長的。針對不定長的 key，一般有這幾種解決辦法：

1.節(jié)點中不存儲實際的 key，而是存儲指向?qū)嶋H tuple 屬性的指針，這樣的話雖然能夠固定大小，但是指針并沒有 key 本身具有的特征，范圍掃描低效，實際使用并不多。

2.節(jié)點的 size 也不固定，來適配不同長度的 key

• 這種方式需要更加精細(xì)化的內(nèi)存管理，并且在 buffer pool 中也需要適配（buffer pool 的 size 通常是固定的），所以實際使用也不多。

3.對齊，總是將 key 對齊為其類型的大小，而不管 key 的 size 有多大。這種方式缺點也顯而易見，就是可能會浪費一定的空間。

4.使用類似 slot page 的組織方式，將 key 存在一個有序的集合中，并且指向其實際的數(shù)據(jù)。

Non-Unique Index

數(shù)據(jù)庫中的索引，有時候可以存在重復(fù)的數(shù)據(jù)，除了唯一索引外。因此，在 B+ Tree 存儲數(shù)據(jù)的時候，需要對重復(fù)的 key 進行處理。

Duplicate Keys

存儲重復(fù) key 很好理解，就是我們可以把重復(fù)的 key 也當(dāng)做是一個單獨的 key 進行存儲即可。

Va

lue List

value list 就是對重復(fù) key 的 value 維護了一個鏈表，將其串聯(lián)起來。

B+ Tree Optimizations

最后再來看下關(guān)于 B+ 樹在設(shè)計時的一些優(yōu)化方案。

Prefix Compression

因為 B+ 樹底層葉子節(jié)點的數(shù)據(jù)是有序排列的，因此存儲在同一個葉子節(jié)點的數(shù)據(jù)，有很大可能是具有相同的特征的，例如可能是類似的，擁有相同的前綴。

所以，針對那些有相同前綴的數(shù)據(jù)，可以只存儲一份前綴數(shù)據(jù)，而不用每個 key 都單獨存儲一份。

Suffix Truncation

前面提到過 B+ 樹中 inner node 只存儲了 key 和索引信息，并不存儲數(shù)據(jù)，只是做為一個輔助查找的索引節(jié)點。因此 inner node 中的 key 并不用是完整的 key，只要能夠起到區(qū)分查找的作用就可以了。

例如上面的例子，由于這兩個 key 所有字符都不一致，因此并不需要存儲完整的 key，只需要存儲能夠幫助查找到下一級節(jié)點的信息就可以了。

Bulk Insert

最好的構(gòu)建 B+ 樹的方式，是將一組有序的數(shù)據(jù)從下到上構(gòu)建 B+ 樹的多級索引，這樣不會存在 B+ 樹的分裂或者合并，效率是最高的。

因此如果有一部分初始化數(shù)據(jù)需要插入到 B+ 樹中，可以先將其排序，然后直接構(gòu)建 B+ 樹。

Pointer Swizzling

B+ 樹遍歷 page 的時候，每次都需要從 buffer pool 中獲取 page 的位置信息，然后 B+ 樹根據(jù)這個位置去獲取 Buffer Pool 中的 page 數(shù)據(jù)。

例如上圖中，需要獲取 page id 為 2 的 page，則會先從 page table 中獲取，Buffer Pool 判斷這個 page 是否在內(nèi)存中，如果不在則加載這個 page 到內(nèi)存，并且返回一個 page 的指針（page 的實際位置）給 B+ 樹。

如果 B+ 樹確認(rèn)掃描到的 page 肯定在內(nèi)存中，那么可以直接存儲 page 指針，省去了從 page table 中尋址的開銷。

這個優(yōu)化比較適用于 B+ 樹的上層節(jié)點，因為 B+ 樹上面的幾層節(jié)點容量相對較小，并且會被頻繁的訪問到，可以緩存到內(nèi)存中加速 B+ 樹的查詢。

Conclusion

這一節(jié)講述了 B+ 樹的一些基本概念，相信讀者能夠?qū)ζ溆幸粋€基本的理解了，在大多數(shù)情況下，B+ 樹是一個在數(shù)據(jù)庫中應(yīng)用非常廣泛的結(jié)構(gòu)。