跳轉到

6.3 B樹簡介#

概念說明#

AVL 與紅黑樹的節點是二元分支，100 萬筆資料樹高約 20——在記憶體中很完美，但若資料在磁碟上，每走一層就是一次磁碟讀取，機械硬碟一次隨機讀取動輒數毫秒，20 次就是數十毫秒，難以接受。

B 樹 重新設計了取捨：與其長得高、每次只取得 1 個鍵，不如每個節點裝很多鍵、同時分出很多岔，把樹變矮。磁碟以「頁（page，如 4KB）」為讀取單位，一個 B 樹節點就設計成恰好一頁：一次讀取拿到數十~數百個鍵，在節點內做陣列二元搜尋（幾乎免費），再跳往下一層。如此一來，100 萬筆資料只需 3~4 層——磁碟讀取次數驟減。

一棵 m 階 B 樹的性質：

  1. 每個節點至多有 m 個小孩、m−1 個鍵。
  2. 除根與葉外，每個節點至少有 ⌈m/2⌉ 個小孩（不會太空）。
  3. 根至少 2 個小孩（若非葉）。
  4. 所有葉在同一層（完美平衡的來源）。
  5. 節點內鍵由小到大排列，作為劃分小孩區間的界標。

B+ 樹 是 B 樹的實務變形：資料只放葉層、葉之間用指標串成有序鏈，內部節點只放導航用的鍵。範圍查詢「撈 2024 年 1 月的所有訂單」只要定位到起點、沿葉鏈掃描即可，這正是 MySQL、PostgreSQL 索引選用 B+ 樹的原因。

Python 實作（B 樹插入）#

插入的步驟：

  1. 從根往下找到合適的葉節點，把鍵插入節點內並保持有序。
  2. 若節點鍵數超過上限（m−1），分裂：把中間鍵上移給父節點，左右各半留在兩個新節點。
  3. 分裂可能向上傳播，最壞情況根也分裂、樹長高一層——這正是「所有葉同層」得以維持的原因。
class BTreeNode:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []
        self.children = []

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

    def insert(self, key):
        root = self.root
        if len(root.keys) == 2 * self.t - 1:   # 根滿 → 先分裂
            new_root = BTreeNode(leaf=False)
            new_root.children.append(self.root)
            self._split_child(new_root, 0)
            self.root = new_root
        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 = t - 1
        mid_key = child.keys[mid]
        right.keys = child.keys[mid + 1:]      # 右半
        child.keys = child.keys[:mid]          # 左半（中間鍵上移）
        if not child.leaf:
            right.children = child.children[mid + 1:]
            child.children = child.children[:mid + 1]
        parent.keys.insert(i, mid_key)
        parent.children.insert(i + 1, right)

    def _insert_nonfull(self, node, key):
        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 search(self, key, node=None):
        node = node or self.root
        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 node
        if node.leaf:
            return None
        return self.search(key, node.children[i])

b = BTree(t=2)                     # 小 t 方便觀察分裂
for x in [10, 20, 5, 6, 12, 30, 7, 17, 3]:
    b.insert(x)

def show(n, d=0):
    if n:
        print("  " * d, n.keys)
        for c in n.children:
            show(c, d + 1)
show(b.root)
print(b.search(12) is not None, b.search(99) is not None)   # True False

複雜度分析#

樹高 h ≤ log_⌈m/2⌉((n+1)/2)——以 m=512 為例，10 億筆資料樹高約 4，即至多 4 次磁碟存取。搜尋/插入/刪除皆 O(log n)（節點內有序陣列的操作與鍵數 m 有關，但 m 視為常數）。空間：節點利用率至少 50%，分裂保證不浪費過多。

練習#

  1. 把 t=2 的 B 樹依序插入 1..20，記錄每次根分裂發生的時機，說明為何所有葉始終同層。
  2. 實作 B 樹的 search 迴圈版本，並寫一個 range_query(lo, hi)（提示：先定位 lo，再中序式掃葉層——若你有實作 B+ 樹則可直接沿葉鏈走）。
  3. 比較「二元 BST 高 20 層」與「m=512 的 B 樹高 4 層」：假設每次磁碟讀取 5ms、記憶體內比較 1ns，估算各需多少時間查一筆資料。