跳轉到

5.3 B+tree 與資料庫索引#

概念說明#

資料庫索引幾乎清一色使用 B+tree 而非 B-tree，差異有三：

  1. 所有資料（記錄指標）只存在葉節點，內部節點只放「路標鍵」。內部節點因此更小、分支因子更大，樹更矮。
  2. 葉節點以雙向鏈結串列相連。範圍查詢 BETWEEN 100 AND 200 只要定位到起點，再沿鏈順序掃描——把隨機 I/O 轉成順序 I/O。
  3. 內部節點的鍵會重複出現在葉層（路標是複本而非資料本身），允許「右偏」實作：分裂時把右半的第一個鍵上移一份。

B+tree 查詢成本 = 樹高 h 次 I/O。以 InnoDB 為例：16KB 分頁、主鍵 8 bytes、指標 6 bytes，內部節點約 1170 路分支；葉節點每頁放 16 筆 1KB 記錄。2000 萬筆資料：葉層約 125 萬頁 → 上兩層 1170 × 1170 ≈ 137 萬 → 樹高 3，即任何主鍵查詢最多 3 次 I/O（根節點與第二層常駐緩衝池時實際只要 1 次）。

叢集索引（clustered index）與二級索引（secondary index）的差別也很關鍵：前者葉節點直接放整筆記錄（資料本身按主鍵組織成 B+tree），後者葉節點放主鍵值，查詢需再回表（bookmark lookup）一次主鍵 B+tree。

演算法步驟：範圍掃描#

  1. 以起點鍵在 B+tree 搜尋，走到葉節點（h 次 I/O）。
  2. 沿葉鏈右移，逐頁輸出滿足範圍的記錄。
  3. 超過終點鍵即停止。若結果占 k 頁，總成本 h + k 次 I/O（順序讀取）。

Python 範例：帶葉鏈的 B+tree#

class Leaf:
    def __init__(self):
        self.keys, self.rec, self.next = [], {}, None
class Node:
    def __init__(self):
        self.keys, self.children = [], []

class BPlusTree:
    def __init__(self, order=4):
        self.root, self.order = Leaf(), order

    def _find_leaf(self, key):
        node = self.root
        while isinstance(node, Node):
            i = 0
            while i < len(node.keys) and key >= node.keys[i]:
                i += 1
            node = node.children[i]
        return node

    def insert_top(self, key, rec):
        up = self._insert(self.root, key, rec)
        if up:                                     # 根分裂 → 樹長高
            k2, right = up
            node = Node()
            node.keys, node.children = [k2], [self.root, right]
            self.root = node

    def _insert(self, node, key, rec):
        """回傳 None 或 (上移鍵, 右新節點)"""
        if isinstance(node, Leaf):
            i = 0
            while i < len(node.keys) and node.keys[i] < key:
                i += 1
            node.keys.insert(i, key); node.rec[key] = rec
            if len(node.keys) <= self.order - 1:
                return None
            mid = self.order // 2
            new = Leaf()
            new.keys = node.keys[mid:]
            new.rec = {k: node.rec[k] for k in new.keys}
            node.keys = node.keys[:mid]
            node.rec = {k: node.rec[k] for k in node.keys}
            new.next, node.next = node.next, new
            return (new.keys[0], new)
        # 內部節點：先遞迴插入子節點
        i = 0
        while i < len(node.keys) and key >= node.keys[i]:
            i += 1
        up = self._insert(node.children[i], key, rec)
        if up is None:
            return None
        k2, right = up
        node.keys.insert(i, k2); node.children.insert(i + 1, right)
        if len(node.children) <= self.order:
            return None
        mid = self.order // 2
        up_key = node.keys[mid]
        rnode = Node()
        rnode.keys = node.keys[mid + 1:]
        rnode.children = node.children[mid + 1:]
        node.keys = node.keys[:mid]
        node.children = node.children[:mid + 1]
        return (up_key, rnode)

    def range_scan(self, lo, hi):
        leaf = self._find_leaf(lo)
        out = []
        while leaf:
            for k in leaf.keys:
                if k > hi: return out
                if k >= lo: out.append(k)
            leaf = leaf.next
        return out

bt = BPlusTree(order=4)
for k in range(1, 21):
    bt.insert_top(k, f"rec{k}")
print("範圍 [5,12]:", bt.range_scan(5, 12))
print("葉鏈是否單調遞增:", bt.range_scan(1, 10**9) == list(range(1, 21)))
print("查詢路徑正確:", all(bt._find_leaf(k) and k in bt._find_leaf(k).rec
                         for k in range(1, 21)))

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

  • 點查詢：h 次 I/O（InnoDB 2000 萬筆約 3 次）。
  • 範圍查詢：h + k 次 I/O，且後項為順序 I/O，單位成本低。
  • 插入（隨機鍵）：h + 分裂成本；鍵遞增插入（如自增主鍵）永遠寫最右葉，分裂成「最右分裂」，無隨機 I/O，吞吐高數倍——這是「自增主鍵較快」的結構性原因。
  • 缺點：二級索引回表多一次隨機 I/O；覆蓋索引（covering index）可避免之。

練習#

  1. 以 order=4 依序插入 1..15，畫出最後的樹與葉鏈。
  2. 計算：分頁 16KB、鍵+指標 14 bytes、記錄 500 bytes 時，1 億筆資料的 B+tree 樹高。
  3. 說明為何「隨機主鍵插入」比「自增主鍵插入」慢，從分頁快取與分裂兩方面分析。