B 樹與 B+ 樹#

為什麼需要 B 樹：為磁碟而生#

紅黑樹這類平衡二元搜尋樹很漂亮，但它們有一個隱含前提：整棵樹都住在記憶體裡。指標一跳，下一個節點就在手邊。

可是資料庫的索引動輒幾 GB，根本塞不進記憶體，只能存在磁碟上。而磁碟 I/O 比記憶體存取慢好幾個數量級——記憶體是奈秒級，磁碟尋址是毫秒級，差了百萬倍。一旦每跳一個節點就要碰一次磁碟，二元樹那套「指標亂跳」的玩法立刻崩潰。

關鍵洞見是：

在磁碟場景下，查找的成本 ≈ 樹高 ≈ 磁碟 I/O 次數。 真正貴的不是 CPU 比較，而是「碰了幾次磁碟」。所以優化目標從「少做比較」變成「把樹壓矮」。

二元樹每個節點只有兩個分支，n 一大樹就很高。一百萬筆資料，二元樹高度約 20 層，意味著一次查找最多要 20 次磁碟 I/O。

B 樹的解法很直接：別只分兩叉，讓一個節點容納很多鍵、伸出很多分支（N 叉）。再把節點大小對齊磁碟的讀取單位（一個 page，通常 4KB 或 16KB），於是：

• 樹變得又矮又寬——同樣一百萬筆，扇出（fan-out）幾百的 B 樹只要 3 到 4 層。
• 一次 I/O 就把一整個節點讀進記憶體，節點內再用二分查找定位要走哪個分支。節點內的比較全在記憶體裡完成，幾乎不花錢。

換句話說，B 樹把昂貴的「磁碟跳轉」次數壓到最低，把廉價的「記憶體比較」次數放大——這正是它為磁碟而生的核心取捨。

B 樹的結構#

B 樹是一棵多叉平衡樹，性質如下：

• 每個節點存放多個有序的鍵；這些鍵把子節點的值域切成數段（k 個鍵 ➡️ k+1 個子節點分支）。
• 每個節點的鍵數被限制在一個區間內（例如介於 d 到 2d 之間），不能太空也不能太滿。
• 插入導致節點過滿時分裂（split），刪除導致節點過空時合併（merge） 或向兄弟節點借鍵，藉此維持平衡。
• 所有葉節點都在同一層（等高），這是 B 樹平衡性的直接保證。

下面是一棵簡化的 3 階 B 樹示意（每個內部節點最多 2 個鍵、3 個分支）：

graph TD
    A["[ 17 | 35 ]"]
    B["[ 8 | 12 ]"]
    C["[ 22 | 28 ]"]
    D["[ 41 | 56 ]"]
    A -->|< 17| B
    A -->|17~35| C
    A -->|> 35| D

讀法：根節點的鍵 17、35 把整個值域切成三段，要找的鍵落在哪一段就走哪個分支。每往下一層代表一次磁碟 I/O，而因為扇出大，層數很少。

B+ 樹（資料庫最常用）#

B+ 樹是 B 樹的一個變形，也是真實資料庫（如 MySQL InnoDB）索引的實際選擇。它和 B 樹的關鍵差異有兩點：

1. 非葉節點只存「鍵」，不存資料——內部節點純粹當作索引、路標，告訴你該往哪走；所有「真正的資料」都只放在葉節點。
2. 葉節點用指標串成一條鏈——相鄰葉節點首尾相連，形成一條有序的雙向鏈。

這兩個改動帶來的好處環環相扣：

• 內部節點不再背負資料，變得非常精簡 ➡️ 同樣大小的 page 能塞下更多鍵 ➡️ 扇出更大 ➡️ 樹更矮，磁碟 I/O 進一步減少。
• 葉節點成鏈 ➡️ 範圍查詢（range query）極其方便：只要先定位到區間起點所在的葉節點，之後沿著鏈一路掃下去即可，完全不必再回頭走內部節點。WHERE age BETWEEN 20 AND 30 這類查詢因此快得驚人。

這正是為什麼 MySQL InnoDB 的索引選用 B+ 樹而非 B 樹。

從 BST、紅黑樹到 B 樹、B+ 樹，這一脈搜尋樹在概念上其實是一以貫之的：都是靠「有序 + 平衡」這兩件事，把查找成本壓到對數級。差別只在於它們各自針對的硬體不同——紅黑樹為記憶體優化，盡量少做比較；B/B+ 樹為磁碟優化，盡量少碰 I/O。理解了這個取捨的軸線，各種搜尋樹就不再是零散的招式，而是同一個核心想法在不同場景下的變體。