跳轉到

5.1 從二元樹到多路搜尋樹#

概念說明#

二元搜尋樹（BST）每個節點只存 1 個鍵、2 個子指標。在記憶體中這沒問題，但在磁碟上，讀取一個節點就是一次 I/O，而一個節點（一個分頁，例如 16KB）其實裝得下數百個鍵——BST 浪費了 99% 以上的分頁空間，讓樹高白白增加。

多路搜尋樹（multiway search tree）的核心想法：一個分頁裝一個節點，節點內放 m 個鍵與 m+1 個子指標。節點內用二分搜尋定位（記憶體速度，近乎免費），樹的分支因子從 2 變成 m，高度從 log₂N 降為 log_mN。

以 16KB 分頁、鍵 8 bytes、指標 8 bytes 計算：每節點約可放 1000 個鍵。一百萬筆資料：BST 高約 20，需 20 次 I/O；1000 路搜尋樹高約 2~3，只需 2~3 次 I/O——快了將近 10 倍。這個「分支因子換 I/O」的槓桿就是磁碟樹狀結構的全部靈魂。

B-tree 是加上平衡條件的多路搜尋樹：所有葉節點在同一層，節點至少半滿（m 路樹每節點至少 ⌈m/2⌉-1 個鍵），確保樹高有保證上界。

演算法步驟：多路搜尋樹查詢#

  1. 讀入根節點分頁（1 次 I/O）。
  2. 在節點的鍵陣列中二分搜尋：找到鍵則回傳；否則選出鍵值區間對應的子指標。
  3. 若為葉節點則查無此鍵；否則讀入子節點分頁（+1 次 I/O），回到步驟 2。

Python 範例：模擬磁碟上的多路搜尋樹 vs BST#

class Disk:
    def __init__(self):
        self.pages, self.io = {}, 0
    def read(self, pid):
        self.io += 1
        return self.pages[pid]

class MultiwayNode:
    def __init__(self, keys, children, pid):
        self.keys, self.children, self.pid = keys, children, pid

class MultiwayTree:
    """簡化版多路搜尋樹：每節點固定 branching 路分支，資料均勻"""
    def __init__(self, disk, branching, n_leaves=1000):
        self.disk, self.b = disk, branching
        self._build(n_leaves)

    def _build(self, n_leaves):
        # 葉節點每個裝 self.b - 1 個鍵的近似模型
        import math
        self.leaves = n_leaves
        level, nodes = 0, n_leaves
        self.height = 0
        while nodes > 1:
            nodes = math.ceil(nodes / self.b)
            self.height += 1

    def search_cost(self):
        return self.disk, self.height

disk = Disk()
# BST 模型：一百萬筆，高 20
def bst_height(n): return 0 if n <= 1 else 1 + bst_height(n // 2)
print("BST（百萬筆）樹高:", bst_height(10**6), "次 I/O")
# 多路：每節點 999 鍵
import math
N = 10**6; m = 1000
height = math.ceil(math.log(N, m))
print(f"多路搜尋樹（{m} 路）樹高: {height} 次 I/O")
print("I/O 比例:", bst_height(10**6) / height, "倍差距")

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

  • 查詢 I/O：O(log_m N)，m 為分支因子。m=1000、N=10⁹ 時僅 3 層。
  • 節點內搜尋：O(log m) CPU，可忽略。
  • B-tree 平衡保證：N 筆鍵、m 路時樹高 ≤ 1 + log_⌈m/2⌉((N+1)/2)，因為節點至少半滿。

練習#

  1. 分頁 8KB、鍵 16 bytes、指標 8 bytes，每節點約放多少鍵？十億筆資料的樹高是多少？
  2. 說明為什麼「節點至少半滿」的條件對磁碟成本是必要的。
  3. 修改範例程式，畫出分支因子 m 從 10 到 1000 時，十億筆資料查詢 I/O 次數的曲線。