Table Index

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

創(chuàng)新互聯(lián)專注于企業(yè)成都全網(wǎng)營銷推廣、網(wǎng)站重做改版、黃山區(qū)網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、成都h5網(wǎng)站建設(shè)、商城網(wǎng)站定制開發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為黃山區(qū)等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

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

B+ Tree 基本概念

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

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

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

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

下圖所示，是一個(gè) B+ Tree 的例子。

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

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

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

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

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

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

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

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

B+ Tree 操作

insert

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

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

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

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

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

delete

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

大致過程如下：

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

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

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

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

B+ Tree Design

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

Node Size

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

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

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

Merge Threshold

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

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

Variable-Length Keys

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

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

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

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

3.對(duì)齊，總是將 key 對(duì)齊為其類型的大小，而不管 key 的 size 有多大。這種方式缺點(diǎn)也顯而易見，就是可能會(huì)浪費(fèi)一定的空間。

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

Non-Unique Index

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

Duplicate Keys

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

Va

lue List

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

B+ Tree Optimizations

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

Prefix Compression

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

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

Suffix Truncation

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

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

Bulk Insert

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

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

Pointer Swizzling

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

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

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

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

Conclusion

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

當(dāng)前名稱：CMU15445學(xué)習(xí)之TreeIndexI
網(wǎng)站路徑：http://uogjgqi.cn/article/djpjjhc.html