B+Tree

你在 Momo 買了一個鍵盤，想查訂單進度。Momo 的訂單資料庫可能有上千萬筆訂單！？（我猜的） 但你按下「查看訂單」，頁面不到一秒就跳出你那筆訂單的物流狀態。 上千萬筆資料存在 SSD 上，Momo 怎麼可能在幾毫秒內找到你那一筆？

如果用暴力法的話，從第一筆訂單開始，一筆一筆比對 order_id，直到找到為止。假設 Momo 有一千萬筆訂單，每筆 record 平均 100 bytes，一個 8 KB 的 disk page 放大約 80 筆，那就是大約 12.5 萬個 page。就算你的 SSD 一次 4KB random read 只要 100 us，掃完 12.5 萬個 page 也要超過 10 秒。

但如果你在 order_id 上建一棵 B+Tree 呢？ B+Tree 的 inner node fan-out 非常高（等等會解釋為什麼，大約 500）。Fan-out 500 代表每個 inner node 可以指向 500 個 child。所以樹的高度只有 $\lceil\log_{500}(10{,}000{,}000)\rceil = 3$ 層。查一筆資料只需要 3 次 disk I/O。 而且 root node 和第二層的 inner node 因為太常被讀，幾乎一直快取在記憶體裡。所以大部分查詢實際上只需要 1 次真正的 disk I/O 就能命中目標 leaf node。

B+Tree 的結構

Inner Node 與 Leaf Node

B+Tree 把 node 分成 inner 和 leaf。inner node（內部節點）只存 routing key 和 child pointer，不存任何實際資料，它就是告訴你「往左走還是往右走」。leaf node（葉節點）才存真正的資料，或是指向資料的 pointer（例如在 PostgreSQL 裡，leaf node 存的是 slotted page 的 CTID）。

很多人會把 B+Tree 和 B-Tree 搞混。在 B-Tree 裡面，inner node 也可以存資料。但 B+Tree 刻意讓 inner node 不存資料，這樣 inner node 就能塞進更多的 routing key，fan-out 更高，樹更矮，disk I/O 更少。

B+Tree 與 Slotted Page 的關係：B+Tree 的 node 本身就是一個 disk page。而 leaf node 裡存的「指向資料的 pointer」，在 PostgreSQL 裡就是 CTID (page ID, slot number)，也就是我們之前學過的 slotted page 裡面那個穩定地址。

下圖來自 Jeremy Cole 對 InnoDB 內部結構的分析：每一層的 page 之間用 doubly linked list 串接，non-leaf page 存的是 child page pointer 而非資料本身。 有興趣可以去看 Jeremy 的文章來瞭解 B+Tree 在 MySQL InnoDB 中的實際運作方式。

Leaf Node 的 Linked List

B+Tree 的 leaf node 之間用 doubly linked list 串在一起。這個設計是為了 range query。假設你要查 WHERE order_id BETWEEN 100 AND 500，B+Tree 先用 search 定位到 order_id = 100 所在的 leaf node，然後沿著 linked list 往右一路掃到 order_id = 500，這樣就不須回到上層 node 重新搜尋。

這和 binary search tree 的 range query 差很多。BST 做 range query 要不斷回到 parent node 判斷要不要走右子樹，traversal 路徑很長。B+Tree 的 leaf linked list 讓 range query 變成簡單的 sequential scan，對 disk I/O 友善。

Fan-out：樹越矮越好

Fan-out 是指一個 inner node 最多能有幾個 child pointer。假設一個 inner node 剛好佔一個 8 KB disk page，每個 routing key 8 bytes，每個 child pointer 6 bytes（page ID），那一個 inner node 可以容納大約 $\lfloor 8192 / (8 + 6)\rfloor = 585$ 個 entry，fan-out 約 585。

用 fan-out $f = 500$ 來算：

• 1 層（root）：指向 500 個 child
• 2 層：$500^2 = 250{,}000$ 個 leaf node
• 如果每個 leaf node 存 100 筆 record：$250{,}000 \times 100 = 25{,}000{,}000$ 筆

兩層 inner node 加一層 leaf，就能索引 2500 萬筆資料。查任何一筆只需要 3 次 disk I/O。而且 root node 和第二層的 inner node 幾乎一直快取在記憶體中（因為太常被讀到了），實際上大部分查詢只需要 1 次真正的 disk I/O 就能命中 leaf node。

Search、Insert、Delete

Search

從 root 開始，在每個 inner node 裡找到正確的 child pointer（通常用 binary search），一路往下走到 leaf node。到了 leaf node 再找到目標 key。每經過一層就是一次 page read。

Insert 與 Delete

Insert：當你要插入一筆新 key，先用 search 找到它應該落在哪個 leaf node。如果 leaf 還有空間，直接插入。如果滿了，就把 leaf 拆成兩半，並把中間的 key 推上去給 parent 作為新的 routing key。這個 split 可能一路往上傳遞。B+Tree 是從 leaf 往上長的。

Delete：先用 search 找到目標 key 所在的 leaf node，把它從 leaf 中移除。如果移除後 node 裡的 key 數量低於下限（通常是半滿），理論上要觸發 merge：先嘗試從 sibling 借一個 key 過來，如果 sibling 也不夠借，就把兩個半空的 node 合併成一個，並從 parent 移除對應的 routing key。這個過程可能往上傳遞，是 split 的反操作。但實務上不少資料庫選擇 lazy merge：不主動合併半空的 node，因為 merge 成本高（要改多個 page 和 parent），而且真實 workload 通常偏 insert-heavy，空間很快又會被填滿。

如果你想深入理解 insert 的 split 過程，可以參考這份教材：B+Tree Insertion (Emory CS)。

B+Tree Insert 跟 Delete 並非本課程重點，知道就好，不用記住。

Prefix Truncation

Inner node 裡的 routing key，其實不需要存完整的 key。它的功能只是「告訴你往左走還是往右走」，所以只要存到能區分左右 child 的最短前綴就夠了。這叫 prefix truncation。

假設一個 inner node 有三個 child（三個 leaf node），分別存 "NCKU"（成大）、"NTHU"（清大）、"NYCU"（交大）的資料。這個 inner node 需要兩個 routing key 來分隔三個 child：

大學縮寫只有 4 個字元，效果就已經不錯。下面的例子以 email 為 key，效果更好："[email protected]"、"[email protected]"、"[email protected]" 三個 key，routing key 不需要存完整的 "[email protected]" 和 "[email protected]"（共 22 bytes），只需要 "B" 和 "C" 各 1 byte 就夠了，省了 91%。key 越長，prefix truncation 省下的空間越多，一個 page 能塞進更多 routing key，fan-out 更高，樹更矮。

B+Tree 是一個很棒的 external data structure

external data structure 指的是存在硬碟上的資料結構，要用的時候才動態載入記憶體。 B+Tree 的每個 node 大小通常設計成等於一個 disk page（常見 4 KB 或 8 KB）。搜尋時每往下走一層，就讀一個 page。這和 disk 的存取模式匹配：disk 的最小讀寫單位就是一個 page（或 block），讀一小段和讀滿整個 page 的成本差異不大，每次讀取就能撈到許多有用的 routing information。

相比之下，binary search tree 每個 node 只存一個 key，一次 disk read 只拿到一個比較結果。如果把 balanced BST 放到 disk 上，查一筆 1000 萬筆資料需要 $\lceil\log_2(10{,}000{,}000)\rceil = 24$ 次 disk I/O。B+Tree 只需要 3 次。差了 8 倍，而且這個差距會隨著資料量增加越來越大。

自問自答

試著用自己的話回答以下問題。如果卡住了，回去重讀對應的段落。

1. 為什麼 B+Tree 要把所有資料都放在 leaf node，而不是像 B-Tree 那樣讓 inner node 也存資料？這個設計決策對 fan-out 和 range query 分別有什麼影響？

2. 假設一棵 B+Tree 的 inner node 大小是 16 KB，每個 routing key 佔 8 bytes，每個 child pointer 佔 6 bytes。請計算 fan-out，以及這棵樹在 4 層的情況下最多能索引多少筆 record（假設每個 leaf node 存 200 筆）。

3. 假設有一張 table 的 primary key 是 VARCHAR(100) 的 email 地址，平均長度 25 bytes。如果沒有 prefix truncation，一個 8 KB inner node 的 fan-out 大約是多少？如果 prefix truncation 能把平均 routing key 長度壓到 5 bytes，fan-out 又會變多少？這對樹高有什麼影響？