跳轉到

5.2 B-tree 的插入刪除與分裂合併#

概念說明#

B-tree（Bayer & McCreight, 1972）是 m 路平衡搜尋樹，滿足：

  1. 根節點至少 2 個子樹（除非是葉）。
  2. 內部節點有 ⌈m/2⌉ 到 m 個子樹。
  3. 所有葉節點在同一層。

插入時從葉往下找位置；若葉滿了就「分裂」：中間鍵上移給父節點，兩半成為新節點。分裂可能向上傳遞，最壞情況一路裂到根，樹高加一——這是 B-tree 唯一長高的方式，因此全樹天然平衡。

刪除從葉移除鍵；若節點低於半滿，先嘗試向相鄰兄弟「借用（rotate）」，不夠借就「合併（merge）」兩兄弟並從父節點下拉一個鍵。合併可能使父節點也低於半滿，於是向上傳遞，最壞情況縮短樹高。

分裂與合併都是「一次處理 2~3 個分頁」的局部操作，I/O 成本與樹高同階，這是 B-tree 能在磁碟上維持平衡的關鍵。

Python 範例：完整 B-tree#

class BTreeNode:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []
        self.children = []
        self.io = 0

class BTree:
    def __init__(self, t=3):          # t = 最小度：節點鍵數 ∈ [t-1, 2t-1]
        self.root = BTreeNode()
        self.t = t

    def search(self, node, key):
        node.io += 1
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and node.keys[i] == key:
            return True
        return False if node.leaf else self.search(node.children[i], key)

    def insert(self, key):
        root = self.root
        if len(root.keys) == 2 * self.t - 1:      # 根滿 → 樹長高
            new = BTreeNode(leaf=False)
            new.children.append(self.root)
            self._split_child(new, 0)
            self.root = new
        self._insert_nonfull(self.root, key)

    def _split_child(self, parent, i):
        t = self.t
        child = parent.children[i]
        right = BTreeNode(leaf=child.leaf)
        mid = child.keys[t - 1]
        right.keys = child.keys[t:]
        child.keys = child.keys[:t - 1]
        if not child.leaf:
            right.children = child.children[t:]
            child.children = child.children[:t]
        parent.keys.insert(i, mid)
        parent.children.insert(i + 1, right)

    def _insert_nonfull(self, node, key):
        node.io += 1
        if node.leaf:
            node.keys.append(key)
            node.keys.sort()
            return
        i = len(node.keys) - 1
        while i >= 0 and key < node.keys[i]:
            i -= 1
        i += 1
        if len(node.children[i].keys) == 2 * self.t - 1:
            self._split_child(node, i)
            if key > node.keys[i]:
                i += 1
        self._insert_nonfull(node.children[i], key)

    def delete(self, key):
        self._delete(self.root, key)
        if not self.root.keys and not self.root.leaf:
            self.root = self.root.children[0]     # 樹高下降

    def _delete(self, node, key):
        node.io += 1
        t = self.t
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and node.keys[i] == key:
            if node.leaf:
                node.keys.pop(i)                  # 情況 1：葉直接刪
            else:
                # 情況 2：內部節點，以前驅鍵取代後遞迴刪除
                pred = self._max(node.children[i])
                node.keys[i] = pred
                self._delete(node.children[i], pred)
            return
        if node.leaf:
            return                                # 鍵不存在
        child = node.children[i]
        if len(child.keys) < t:                   # 情況 3：子節點半滿不足
            self._fix_child(node, i)
            child = node.children[i]
        self._delete(child, key)

    def _max(self, node):
        while not node.leaf:
            node = node.children[-1]
        return node.keys[-1]

    def _fix_child(self, node, i):
        t = self.t
        left = node.children[i - 1] if i > 0 else None
        right = node.children[i + 1] if i + 1 < len(node.children) else None
        if left and len(left.keys) >= t:          # 向左兄弟借
            child = node.children[i]
            child.keys.insert(0, node.keys[i - 1])
            node.keys[i - 1] = left.keys.pop()
            if not child.leaf:
                child.children.insert(0, left.children.pop())
        elif right and len(right.keys) >= t:      # 向右兄弟借
            child = node.children[i]
            child.keys.append(node.keys[i])
            node.keys[i] = right.keys.pop(0)
            if not child.leaf:
                child.children.append(right.children.pop(0))
        elif left:                                # 合併左兄弟
            left.keys += [node.keys.pop(i - 1)] + node.children[i].keys
            left.children += node.children[i].children
            node.children.pop(i)
        elif right:                               # 合併右兄弟
            child = node.children[i]
            child.keys += [node.keys.pop(i)] + right.keys
            child.children += right.children
            node.children.pop(i + 1)

t = BTree(t=2)   # 2-3-4 樹
for k in [10, 20, 5, 6, 12, 30, 7, 17, 3, 25, 1, 40, 8]:
    t.insert(k)
print("查詢 12:", t.search(t.root, 12), "| 查詢 99:", t.search(t.root, 99))
t.delete(6); t.delete(12)
print("刪除後 查詢 6:", t.search(t.root, 6), "| 查詢 7:", t.search(t.root, 7))

tree = BTree(t=3)
for k in range(1, 200):
    tree.insert(k)
def height(n):
    return 1 if n.leaf else 1 + height(n.children[0])
print("插入 199 鍵後樹高（根=第1層）:", height(tree.root))

複雜度與 I/O 成本分析#

  • 查詢：O(log_t N) 次節點存取 ≈ 樹高次 I/O。
  • 插入：一次根到葉的路徑（h 次 I/O）；若用「預防性分裂」（下行時把滿節點先裂開），一路只需寫回路徑，總計約 2h+ 次 I/O，無需回溯。
  • 刪除：同階，最壞情況合併向上傳遞整條路徑，約 3h 次 I/O。
  • 實務：h 通常 3~4，一次更新 = 數次隨機 I/O + 日誌寫入，故資料庫把索引維護視為交易成本的一部分。

練習#

  1. 以 t=2（2-3-4 樹）依序插入 1..10，畫出每次觸發分裂後的樹。
  2. 依序刪除 1..5，標示每步是「借用」還是「合併」。
  3. 說明「預防性分裂」為何能把插入從「下行＋回溯」變成單趟下行，對 I/O 有何影響。