[[437658]]

本文轉(zhuǎn)載自微信公眾號(hào)「小菜學(xué)編程」，作者fasionchan 。轉(zhuǎn)載本文請聯(lián)系小菜學(xué)編程公眾號(hào)。

前面我們介紹了 哈希索引 和 LSM樹索引 ，它們都基于日志結(jié)構(gòu)式的數(shù)據(jù)文件。雖然工程界對這種索引的認(rèn)可度正與日俱增，但還遠(yuǎn)不是最受歡迎的索引技術(shù)。

那么，目前應(yīng)用最廣的索引技術(shù)又是什么呢?

您可能早就有所耳聞——這就是本文要探討的 B樹( b-tree )索引。B樹可以說是數(shù)據(jù)庫索引技術(shù)中的武林盟主，能夠幾十年長盛不衰，必定有它自己的獨(dú)門秘訣。

索引結(jié)構(gòu)

跟我們在 LSM樹 一節(jié)中提到的 SSTable 一樣，B樹也是將數(shù)據(jù)組織成有序形式，因此支持范圍查詢。盡管如此，它們的底層結(jié)構(gòu)卻完全不同，B樹有自己獨(dú)特的設(shè)計(jì)哲學(xué)。

日志結(jié)構(gòu)式索引將數(shù)據(jù)分成大小可調(diào)節(jié)的分段，通常是幾兆或更大，然后再順序?qū)懭氪疟P。而B樹則是以 塊( block )為單位來組織數(shù)據(jù)，塊大小是固定的，通常是 4KB ，也可以更大。這種設(shè)計(jì)更貼近磁盤的硬件結(jié)構(gòu)，因?yàn)榇疟P也是以塊為單位來讀寫數(shù)據(jù)的。

出于性能方面考慮，計(jì)算機(jī)通常以一定字節(jié)數(shù)(如 4KB )為單位來存取數(shù)據(jù)。在不同的場景有不同的叫法：磁盤數(shù)據(jù)一般稱為 塊 ( block )，內(nèi)存數(shù)據(jù)一般稱為 頁( page )。這兩種場景數(shù)據(jù)庫均有涉及，因而術(shù)語可以混用。

磁盤中的每個(gè)數(shù)據(jù)塊都有一個(gè)唯一的地址，因此數(shù)據(jù)塊間可以互相引用，有點(diǎn)像內(nèi)存中的指針。因此，我們可以用這種方式，將數(shù)據(jù)塊組織成一棵樹——B樹( b-tree )。

如上圖，為簡化討論，我們假設(shè)數(shù)據(jù)庫記錄只有兩個(gè)字段：一個(gè)是索引鍵，類型為整數(shù);另一個(gè)是值。數(shù)據(jù)按索引鍵排序，依次保存在一個(gè)數(shù)據(jù)塊中，如藍(lán)色數(shù)據(jù)塊所示。

紫色部分?jǐn)?shù)據(jù)塊為索引，它將索引鍵的范圍劃分為多個(gè)區(qū)間;每個(gè)區(qū)間保存著另一個(gè)數(shù)據(jù)塊的地址( ref )，表示該范圍內(nèi)的數(shù)據(jù)，可以通過 ref 指向的數(shù)據(jù)塊找到。上圖中紅色的 ref 表示， 之間的數(shù)據(jù)，可以通過其左下方的另一個(gè)索引數(shù)據(jù)塊找到。

如果子范圍內(nèi)的數(shù)據(jù)記錄還很多，單個(gè)數(shù)據(jù)塊容納不下，ref 便指向另一個(gè)索引塊，進(jìn)一步將數(shù)據(jù)范圍分小;如果子范圍內(nèi)的數(shù)據(jù)記錄不多，一個(gè)數(shù)據(jù)塊就能裝下，ref 便直接指向數(shù)據(jù)。

這樣一來，ref 就將數(shù)據(jù)塊組織成一棵多叉樹，數(shù)據(jù)塊主要分為兩種：

• 一種用于保存數(shù)據(jù)記錄，如上圖藍(lán)色部分，位于樹的 葉子節(jié)點(diǎn) ，簡稱 數(shù)據(jù)塊 ;
• 一種用于保存索引，如上圖紫色部分，位于樹的的 內(nèi)部節(jié)點(diǎn)，簡稱 索引塊 ;

從樹的根節(jié)點(diǎn)索引塊出發(fā)，根據(jù)數(shù)據(jù)鍵所在范圍的 ref 逐層往下找，即可定位到數(shù)據(jù)記錄。舉個(gè)例子，當(dāng)查詢鍵為 400 的記錄時(shí)，搜索路徑如綠色箭頭線所示：

從根索引塊出發(fā)，400 落在區(qū)間 [343, 470) ，根據(jù)該區(qū)間 ref 找到下一級(jí);

來到下一個(gè)索引塊，400 落在區(qū)間 [384, 412) ，根據(jù)該區(qū)間 ref 找到下一級(jí);

最終來到藍(lán)色的數(shù)據(jù)塊，待查找的數(shù)據(jù)記錄就在里面;

范圍查詢

為了支持范圍查詢，數(shù)據(jù)庫將數(shù)據(jù)記錄排過序后才保存到數(shù)據(jù)塊，相鄰數(shù)據(jù)塊間則通過雙向鏈表指針連接在一起。

這樣一來，數(shù)據(jù)庫只要先定位邊界元素，然后以此為起點(diǎn)遍歷數(shù)據(jù)即可：

如果查詢條件為小于，則從后往前遍歷數(shù)據(jù);

如果查詢條件為大于，則從前往后遍歷數(shù)據(jù);

如上圖，以查詢大于等于 400 且小于 420 的數(shù)據(jù)為例：

數(shù)據(jù)庫定位到鍵值為 400 的數(shù)據(jù)記錄，如紅框所示;

數(shù)據(jù)庫檢查本數(shù)據(jù)塊內(nèi) 400 以后的記錄，滿足小于 420 則取出;

數(shù)據(jù)庫根據(jù)鏈表指針找到下一個(gè)數(shù)據(jù)塊，繼續(xù)檢查里面的數(shù)據(jù)記錄，滿足小于 420 則取出;

數(shù)據(jù)庫重復(fù)步驟 3 ，逐個(gè)往后遍歷數(shù)據(jù)塊，直到有數(shù)據(jù)記錄大于等于 420 ;

分支因子

我們注意到，B樹是一種多叉樹。那么，為什么不能用最簡單的二叉樹呢?

實(shí)際上，每個(gè)樹節(jié)點(diǎn)最多可以有多少個(gè)分叉，是樹的一個(gè)非常重要的特性—— 分支因子( branching factor )。我們知道，在數(shù)據(jù)記錄數(shù)一定的前提下，樹的分支因子越大，高度越低。

我們使用排序樹來查找數(shù)據(jù)時(shí)，從根節(jié)點(diǎn)開始不斷搜索，最終來到葉子節(jié)點(diǎn)。換句話講，我們需要檢查的節(jié)點(diǎn)數(shù)，其實(shí)就是樹的高度。

而數(shù)據(jù)庫數(shù)據(jù)需要持久化并保存在磁盤里面，那磁盤有什么特點(diǎn)呢?

• 磁盤 IO 比較慢，非順序的磁盤 IO 更是如此;
• 磁盤 IO 以 塊( block )為數(shù)據(jù)單位，單次 IO 總是讀寫整個(gè)塊;

在排序樹中搜索數(shù)據(jù)，顯然是離散讀，而不是順序讀。因?yàn)槲覀儫o法保證 ref 指向的數(shù)據(jù)塊就在當(dāng)前塊后面，磁盤通常只能重新 尋道( seek )后才能讀取數(shù)據(jù)。由于磁盤尋道很慢很慢，IO 次數(shù)必須盡量減少，因此樹的高度應(yīng)該盡量壓低。

另一方面，磁盤以塊為單位讀寫數(shù)據(jù)，一個(gè)塊可以保存很多分支信息。如果一個(gè)塊只保存兩個(gè)分支，那就浪費(fèi)了。因?yàn)榫退阒槐４鎯蓚€(gè)分支，讀的時(shí)候還是必須整塊讀，開銷是一樣的。因此，不如盡量提高分支數(shù)，這樣還能減低樹的高度，進(jìn)而減少 IO 次數(shù)。

通常 4KB 大的數(shù)據(jù)塊可以保存多達(dá) 500 個(gè)分支，如果樹的高度為 3 ，可以支撐多達(dá) 個(gè)數(shù)據(jù)，超過一億。有意思的是數(shù)據(jù)庫根索引塊通常緩存在內(nèi)存中，這樣只需 2 次 IO 操作即可從超過 1 億數(shù)據(jù)中找到想要的那個(gè)。

綜上所述，B樹幾乎就是為磁盤量身定制的數(shù)據(jù)結(jié)構(gòu)，它充分地利用了磁盤的特點(diǎn)：

磁盤以塊為單位讀寫數(shù)據(jù)，B樹就以塊為節(jié)點(diǎn)，組織成多叉樹;

磁盤 IO 很慢，B樹就通過提高分支因子，降低樹的高度，減少 IO 次數(shù);

寫操作

數(shù)據(jù)庫寫操作分為兩種，一種是 更新( update )，一種是 插入( insert )。

如果要更新數(shù)據(jù)庫中的已有記錄，先搜索B樹找到包含該記錄的數(shù)據(jù)塊(葉子節(jié)點(diǎn))。然后修改數(shù)據(jù)塊的記錄值，再將個(gè)數(shù)據(jù)塊寫回磁盤。由于數(shù)據(jù)塊只是內(nèi)容改變了，位置不變，因此B樹中任何對該數(shù)據(jù)塊的引用仍然有效。

如果要插入一條新記錄，同樣先搜索B樹，找到數(shù)據(jù)范圍包含新記錄的數(shù)據(jù)塊(葉子節(jié)點(diǎn))。如果數(shù)據(jù)塊還有足夠空間，就將新記錄添加進(jìn)入并保存到磁盤即可。如果數(shù)據(jù)塊空閑空間不足，則需要將其分裂為兩個(gè)：

如上圖，以插入 399 為例：由于目標(biāo)數(shù)據(jù)塊已經(jīng)存滿，需要將其分裂為兩個(gè)。分裂后的數(shù)據(jù)塊都只有一半數(shù)據(jù)，新記錄保存在其中的一個(gè)。

如果新記錄的鍵相對較小，則保存在左邊的數(shù)據(jù)塊;否則就保存在右邊的數(shù)據(jù)塊。399 跟該范圍的其他數(shù)據(jù)相比較小，因此保存在左邊數(shù)據(jù)塊。

由于數(shù)據(jù)塊發(fā)生了分裂，因此它們的父節(jié)點(diǎn)需要更新，以便記錄最新的數(shù)據(jù)范圍和分支信息。

B樹算法可以保證樹的 平衡( balanced )：一棵包含 個(gè)鍵的B樹，高度不超過 ，否則樹的性能會(huì)大打折扣。通常一棵 3 層或 4 層深的B樹即可容納數(shù)據(jù)庫所有數(shù)據(jù)，因此查詢時(shí)無須遍歷太多數(shù)據(jù)塊，性能相對較好。

至此，三種主流的數(shù)據(jù)庫索引技術(shù)已經(jīng)全部介紹完畢。除了本節(jié)介紹的B樹索引，其他兩種分別是：

• 哈希索引
• LSM樹索引