B 樹：磁碟巨人

演算法背後的故事：矮個子圖書管理員

想像一個擁有 10 億本書的圖書館。

• 場景 A (二叉樹)： 為了找一本書，妳從入口開始。「左還是右？」妳向左。「左還是右？」妳向右。妳可能需要穿過 30 道門（樹的高度）才能找到書。
• 場景 B (B 樹)： 圖書管理員很矮，但胳膊很長。在入口處，他手裡拿著 1000 張索引卡。他說：「書在 452 號房間。」妳走到 452 號房間。那裡，另一位管理員拿著 1000 張卡片。「12 號架子。」妳走到 12 號架子。找到了。

在場景 B 中，妳只穿過了 3 道門。 為什麼？因為每個節點（管理員）掌握的資訊量大得多。

這就是 B 樹。它是為 硬碟 設計的，在那上面，「走路」（尋道）很慢，但「閱讀」（傳輸數據）很快。

為什麼需要它？

• 資料庫： MySQL (InnoDB), PostgreSQL, SQLite 都使用 B 樹（或 B+ 樹）作為索引。
• 檔案系統： NTFS (Windows), HFS+ (Mac), XFS 都使用 B 樹來追蹤檔案。
• 為什麼不用 BST？ 磁碟上的 BST 查找一條記錄需要 30 次隨機尋道，耗時約 300ms。B 樹只需要 3 次 (~30ms)。

演算法是如何「思考」的

這個演算法是一個多路管理者。

1. 胖節點： 一個節點不是擁有 1 個鍵和 2 個孩子，而是擁有多達 $M$ 個鍵和 $M+1$ 個孩子（例如 M=1000）。
2. 排序： 節點內部的鍵是有序的。我們可以在節點內部使用二分搜尋（因為數據在 RAM 中，所以很快）。
3. 生長：
   • 插入發生在 葉子 處。
   • 如果葉子滿了，它會從中間 分裂。中間的鍵被踢給父親。
   • 如果父親也滿了，它也分裂。
   • 樹是向上生長的，根節點始終在頂部。

工程決策：B 樹 vs. B+ 樹

在實踐中，幾乎所有人都使用 B+ 樹 變體。

• B 樹： 數據儲存在所有節點中。
• B+ 樹： 數據只儲存在葉子中。內部節點只是路標（鍵）。葉子透過鏈表連結在一起。
  • 好處： 掃描「ID 從 100 到 200 的所有用戶」超級快。妳只需找到 100，然後沿著葉子的鏈表走即可。

實作參考 (Python 概念版)

實作一個 B 樹是 500 行代碼級別的工程。這裡展示搜尋邏輯，以體現「多路」特性。

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

def search(node, k):
    # 找到第一個大於或等於 k 的鍵
    i = 0
    while i < len(node.keys) and k > node.keys[i]:
        i += 1
    
    # 1. 在此節點中找到了嗎？
    if i < len(node.keys) and node.keys[i] == k:
        return (node, i)
    
    # 2. 如果是葉子，說明找不到了
    if node.leaf:
        return None
        
    # 3. 遞迴進入正確的孩子
    return search(node.children[i], k)

# 魔法在於 'node.children[i]' 將搜尋空間縮小了 
# M 倍（例如 1000），而不僅僅是 2 倍。

小結

B 樹教會我們：硬體決定結構。當移動成本（磁碟 I/O）很高時，妳應該在一次行程中攜帶儘可能多的東西。它提醒我們，高效的軟體不僅僅關於 $O(N)$，更關乎理解機器的物理現實。