學習手記：2018清華大學DB/AI Bootcamp — II — B-Tree Indexing

前言

本篇為系列中第二篇文章。延續前一篇的內容，講述同樣為現代 Database System 亦廣泛實作的 Indexing 機制 － B-Tree Index 。

B-Tree

雖然 Hash-Based Index 運作非常快速（存取時間接近 O(1)），但無法進行範圍性的索引為其硬傷，致使其應用場景有限。因此現代 Database System 多實作有基於 B-Tree 資料結構的 B-Tree Index 作為索引方式。要理解 B-Tree Index ，就必須先對 B-Tree 有所認知。

基本的 B-Tree 如下所示：

B-Tree 具備如下特性：

1. 每一棵 B-Tree 都需要在建立前指定好 Minimal Degree ， t 。
2. 樹上的每個節點內存放最少 t-1 個 keys ，最多 2t-1 個 Keys。
3. Root Node 較為特殊，允許存放最少 1 個 Key ，最多 2t-1 個 Keys。
4. 每個節點當下擁有的子節點數為 節點當下擁有的 key 數 + 1
5. 每個節點上的 Keys 都是以升序（ Increasing Order ）排列，相隔的兩 Key ，K1、 K2 ，之間的任一子節點上的任一 Key ，其值必落在 K1 - K2 之間。
6. 所有葉節點 （Leaf Node ）的深度（ Depth ）必定相同。

1. Search

B-Tree 的 Search 從 Root Node 開始，比對目標 Key 與所在節點上的 Key 的值。若目標 Key 的值：

1. 小於最小Key，就往節點上最左方的子節點往下移動。
2. 落在某二鄰近 Key 之間，就往此二鄰近 Key 之間的子節點往下移動。
3. 大於最大Key，就往節點上最右方的子節點往下移動。

重複直到找到相符或找到葉節點還找不到為止。

2. Insert

往 B-Tree 中 Insert 新的 Key ，K ，的過程稍微繁複，遵照如下流程而行：

範例

要在如下的 t=2 之 B-Tree 內加入一值為 350 之 Key

1. 起始建立 X 於 Root Node 之上， Root Node 為 Y。

2. Y 內節點數達到上限，需要以 200 為界分開為兩子樹，並將 200 拉升到 X 。由於此時 350 應往 200 右方的子樹，所以 200 右方子樹成為新的 X 。

3. 由於 350 應移動往 250 右方子樹，因此 250 右方子樹成為新的 Y 。

4. Y 內節點數達到上限，需要以 300 為界分開為兩子樹，並將 300 拉升到 X 。由於此時 350 應往 300 右方的子樹，所以 300 右方子樹成為新的 X 。

5. 此時 X 已為 Leaf Node，直接將350插入，結束流程。

由流程可以看出， B-Tree 的高度可視作由 Leaf Node 往 Root Node 方向成長，如此一來，便能讓所有 Leaf Node 都保持在同一 Depth 上。雖然原作者並沒有給明 B-Tree 中，B 一字母的涵義，但後人一般將之視為 Blance，即平衡、穩固之意，正如 B-Tree 所呈之結構。

3. Delete

相較於 Search 及 Insert ， Delete 的規則最為複雜。基本流程都是自 Root Node 開始逐層向下調整 B-Tree 結構：

範例：刪除 Leaf Node

1. 起始 t=2 之 B-Tree 如下，目標為自其中刪除 Key = 75

2. 將 Root Node 定為起始移動位置 X ，此時 75 位於 以 Left Child 作為 Root Node 之子樹之中，因此將 Left Child 定為 X.C

3. 由於 X.C 不足 t=2 組 Key ，而 Left / Right Sibling 上亦皆不足 t=2 組 Key ，因此將 X.C 與其 Sibling 合併（ Right Sibling ）。此時自 X 上移動介於兩者之間的 Key （ 100 ）往下至兩者間之位置，並將兩者合併

4. 重新搜尋 75 之位置，界於 50 與 100 間往下的 Child 上，重新指定 X 與 X.C0

5. 此時 X.C 不足 t=2 把 Key ，而 Right Sibling 尚有 t-1=1 把 Key 。將 X 上置於 X.C 後的 Key （ 100 ） 移向 X.C 最末，並抽取 Right Sibling 上第一把 Key 至 X 上空缺之位。

6. 此時 X 上有目標 Key = 75 ，又 X 為 Leaf Node ，直接將目標 Key 刪除，結束流程

範例：刪除 Internal Node

1. 起始 t=2 之 B-Tree 如下，目標為自其中刪除 Key = 275

2. 將 Root Node 定為起始移動位置 X ，此時 275 位於 以 Right Child 作為 Root Node 之子樹之中，因此將 Right Child 定為 X.C

3. 由於 X.C 不足 t=2 組 Key ，而 Left / Right Sibling 上亦皆不足 t=2 組 Key ，因此將 X.C 與其 Sibling 合併（ Left Sibling ）。此時自 X 上移動介於兩者之間的 Key （ 100 ）往下至兩者間之位置，並將兩者合併

4. 將前一步 X.C 定為 X ，此時發現目標 Key ， 275 ， 在 Internal Node 上，而 275 的 Left Child 至少擁有 t=2 把 Key ，因此先向 Left Child 往下搜尋其子樹中，最右邊的 Leaf Node ，定為 Predecessor

5. 將目標 Key （ 275 ）的內容替換為 Predecessor ，而欲刪除的目標 Key 改為 Predecessor （250）

6. 自前一步的 Left Child 開始往下執行刪除目標 Key 的流程，將Left Child定為 X ，發現 250 即位於其上，且 X 為 Leaf Node ，直接刪除，結束流程

B-Tree Index

實務上利用 B-Tree 作為 Index 的時候， Node 被稱為 Directory Page ，Leaf Node 被稱為 Leaf Page 。另外有如下額外限制：

1. Tree 的高度有限制，無法無限增長
2. Node 只儲存 Key ，不儲存完整的 Index 資訊
3. 完整的 Index 資訊只儲存在 Leaf Node 中

所以用於 Indexing 的 B-Tree 形式會如下所示：

可以見到，即使 Directory Page 中有 Key ，還是需要下探到 Leaf Page 才能取得真正的 Index。而 Leaf Page 中最大可儲存的 Index 量不在 B-Tree 限制中，可以額外指定。但由於須因應限制 1. ，因此在高度不允許擴充時，可以額外加掛 Overflow Block 在 Leaf Node 上：

在 Leaf Page 以及加掛的 Overflow Block 上， Index 還是保持排序關係，以利搜尋：

Insert

在 Insert 過程中，由於1.的限制，如果已經沒有更多空間讓樹成長，就會直接將 Key 插入於 Leaf Page 上。其餘狀況中，則除了在 Directory Page 中插入 Key 外，還需下探到 Leaf Page 上插入 Index 資訊。

Delete

Delete 過程中， 除了將 Directory Page 中的 Key 刪除外，還需要在下探到 Leaf Page 中刪除對應的 Index 資訊。

Implement

B-Tree Index 除可進行範圍搜尋外，其受青睞原因亦為其時間複雜度：

• Equality Search 與 Update 的時間複雜度為 O(log(record數))
• Range Search 的時間複雜度為 O(record數)

然而實作上為求節省空間和增加速度，還有不少取捨與變形，此部分就不在本文論述的範圍內，可以參考其它 Database System 或 Vanilla DB 的設計。

外部參考資料

1. GeeksForGeek — B-Tree | Set 1 (Introduction)
2. GeeksForGeek — B-Tree | Set 2 (Insert)
3. GeeksForGeek — B-Tree | Set 3 (Delete)
4. University of San Francisco 的 B-Tree 的 Live Demo
5. 課程投影片