第九章 B樹（B-tree、B-樹）

B樹是一種平衡的多路搜尋樹，多用于檔案系統、資料庫的實作；

• 仔細觀察B樹，有什麼眼前一亮的特點？

• 1 個節點可以存儲超過 2 個元素、可以擁有超過 2 個子節點

• 擁有二叉搜尋樹的一些性質
• 平衡，每個節點的所有子樹高度一緻
• 比較矮

m階B樹的性質（m>=2）

如果 m = 2，那B樹是什麼樣子？

• 二叉搜尋樹

資料庫實作中一般用幾階B樹？

• 200 ~ 300

B樹 vs 二叉搜尋樹

• B樹和 二叉搜尋樹，在邏輯上是等價的
• 多代節點合并，可以獲得一個超級節點

• 2 代合并的超級節點，最多擁有 4 個子節點（至少是 4 階B樹）
• 3 代合并的超級節點，最多擁有 8 個子節點（至少是 8 階B樹）
• n 代合并的超級節點，最多擁有 2^n 個子節點（ 至少是 2^n 階B樹）

• m 階 B樹，最多需要 log2m 代合并

搜尋

跟二叉搜尋樹的搜尋類似：

1. 先在節點内部從小到大開始搜尋元素
2. 如果命中，搜尋結束
3. 如果未命中，再去對應的子節點中搜尋元素，重複步驟 1

添加 – 上溢

• 新添加的元素必定是添加到葉子節點

• 插入55

• 插入95

• 再插入 98 呢？（假設這是一棵 4階B樹）

• 4階B樹最多存儲3個元素

• 最右下角的葉子節點的元素個數将超過限制
• 這種現象可以稱之為：上溢（overflow）

添加 – 上溢的解決(假設5階)

• 上溢節點的元素個數必然等于m
• 假設上溢節點最中間元素的位置為k

• 将 k 位置的元素向上與父節點合并

• 将[0, k - 1]和[k + 1, m - 1]位置的元素分裂成 2 個子節點

• 這 2 個子節點的元素個數，必然都不會低于最低限制（┌ m/2 ┐ − 1）

• 一次分裂完畢後，有可能導緻父節點上溢，依然按照上述方法解決

• 最極端的情況，有可能一直分裂到根節點

添加示例：假設是4階B樹

• 插入98：

• 插入52：

• 插入54：

删除

删除 – 葉子節點

• 假如需要删除的元素在葉子節點中，那麼直接删除即可
• 删除30：

删除 – 非葉子節點

• 假如需要删除的元素在非葉子節點中

1. 先找到前驅或後繼元素，覆寫所需删除元素的值
2. 再把前驅或後繼元素删除

• 删除60：

• 非葉子節點的前驅或後繼元素，必定在葉子節點中

• 是以這裡的删除前驅或後繼元素 ，就是最開始提到的情況：删除的元素在葉子節點中

• 真正的删除元素都是發生在葉子節點中

删除 – 下溢

• 删除 22？（假設這是一棵 5階B樹）

• 葉子節點被删掉一個元素後，元素個數可能會低于最低限制（​

  ​≥​

  ​ ┌ m/2 ┐ − 1 ）

• 這種現象稱為：下溢（underflow）

删除 – 下溢的解決

• 下溢節點的元素數量必然等于┌ m/2 ┐ − 2
• 如果下溢節點臨近的兄弟節點，有至少 ┌ m/2 ┐ 個元素，可以向其借一個元素

• 将父節點的元素 b 插入到下溢節點的 0 位置（最小位置）

• 用兄弟節點的元素a（最大的元素）替代父節點的元素b
• 這種操作其實就是：旋轉

• 如果下溢節點臨近的兄弟節點，隻有 ┌ m/2 ┐ − 1 個元素

• 将父節點的元素 b 挪下來跟左右子節點進行合并

• 合并後的節點元素個數等于┌ m/2 ┐ + ┌ m/2 ┐ − 2，不超過 m − 1
• 這個操作可能會導緻父節點下溢，依然按照上述方法解決，下溢現象可能會一直往上傳播

删除示例：

4階B樹

• 如果先學習 4 階 B 樹（2 - 3 - 4 樹），将能更好地學習了解紅黑樹：
• 4階B樹的性質：

• 所有節點能存儲的元素個數 x ：1 ≤ x ≤ 3

• 所有非葉子節點的子節點個數 y ：2 ≤ y ≤ 4
• 添加：從 1 添加到 22

• 删除：從 1 删除到 22