平衡 BST 教材把 B 樹列成「磁碟用的多路樹」，但沒有一次插入分裂的推演。記憶體內的紅黑樹每個節點只有一個鍵，磁碟一次讀寫卻是一整頁。B 樹讓一個節點裝滿一頁，樹高跟著頁數的對數走，而不是鍵數的對數乘上一個很大的常數。
相關教材：Tree_Teaching_Materials.md、Balanced_BST_Teaching_Materials.md。
目錄
1. 為什麼不是紅黑樹
紅黑樹的高度是 (\Theta(\log_2 n))。每一層若都是一次磁碟讀取，百萬個鍵大約要 20 次讀取。
磁碟與 SSD 的傳輸單位是頁，常見 4 KiB 或更大。一次讀取的成本在「有沒有讀到這一頁」，不在這一頁裡比較了 3 次還是 300 次。B 樹把數百個鍵放在同一個節點，分支數是數百，高度常常是 3 或 4。比較次數變多，磁碟次數變少。這是資料庫索引與檔案系統目錄的標準形狀。
記憶體內、鍵是一個字、還要做旋轉的教學題，仍然用 AVL 或紅黑樹。不要在 RAM 裡為了「比較進階」去實作 B 樹，常數通常更差。
2. 定義
固定最小度 (t \ge 2)。
- 每個節點最多 (2t-1) 個鍵，所以是滿的時候有 (2t) 個孩子。
- 除了根，每個節點至少 (t-1) 個鍵。
- 根至少有一個鍵（空樹除外）。
- 節點裡的鍵遞增。
- 有 (k) 個鍵的內部節點有 (k+1) 個孩子。孩子 (i) 的鍵都小於第 (i) 個鍵，孩子 (i+1) 的鍵都大於第 (i) 個鍵。
- 所有葉子在同一層。
(t=2) 時每個節點 1 到 3 個鍵，就是 2-3-4 樹。下面的推演用 (t=2)，手算才看得完。真實資料庫的 (t) 是數百。
3. 搜尋
從根開始。在節點裡用二元搜尋找鍵。找到就結束。找不到就走進「夾住這個搜尋鍵」的那一個孩子。走到葉子還沒有，就是不存在。
成本是 (O(\log_t n)) 次節點讀取，每個節點內部再 (O(\log t)) 或 (O(t)) 次比較。磁碟模型只數節點讀取。
4. 插入與分裂
新鍵總是插到葉子。若葉子還有空位（鍵數 (< 2t-1)），照順序插入。
若節點已滿，先分裂再往下走（由上而下），這樣插入時不會遇到滿節點，也不需要再往上連鎖處理。
分裂一個滿節點（(2t-1) 個鍵）：中間那個鍵上升到父親，左半與右半各留 (t-1) 個鍵，成為兩個兄弟。(t=2) 時滿節點是 3 個鍵，中間上升到父親，左右各剩 1 個鍵。
根滿了就長高一層：新的根只有原先的中間鍵，這是 B 樹變高的唯一方式。所以葉子永遠同層。
5. 完整推演
(t=2)，依序插入 10, 20, 5, 6, 12, 30, 7, 17。
10：根[10]。20：根[10, 20]。5：根[5, 10, 20]。已經滿了。- 插入
6之前先分裂根。中間鍵10上升，新根[10]，左[5]，右[20]。6進入左邊，變成[5, 6]。
[10]
/ \
[5, 6] [20]12進入右邊：[12, 20]。30進入右邊：[12, 20, 30]。右邊滿了。- 插入
7時左邊[5, 6]未滿，直接變成[5, 6, 7]。右邊先不動。 - 插入
17之前，右邊已滿，先分裂。中間鍵20升到根。根從[10]變成[10, 20]。原右邊分成[12]與[30]。
[10, 20]
/ | \
[5, 6, 7] [12] [30]17 落在中間那個孩子（大於 10、小於 20），中間變成 [12, 17]。
[10, 20]
/ | \
[5, 6, 7] [12, 17] [30]檢查定義：根有 2 個鍵，每個內部節點的孩子數是鍵數加一，葉子同層，沒有節點超過 3 個鍵，非根節點至少 1 個鍵。搜尋 17 會走中間孩子並找到。搜尋 18 也走中間孩子（18 介於根的 10 與 20 之間），在葉子 [12, 17] 裡比 17 大、又沒有下一層，所以找不到。它不會跑到右邊的 [30]，因為 18 小於根上的 20。
6. 刪除的策略
刪除比插入長，但策略只有三個方向。
- 鍵在葉子：直接刪，若節點鍵數少於 (t-1)，再修復。
- 鍵在內部：用左子樹最大或右子樹最小（一定在葉子）換上來，問題化成刪葉子。
- 節點太瘦：向左或右兄弟借一個鍵（父親的鍵下來，兄弟的邊界鍵上去），或與兄弟合併，父親的一個鍵下降。合併可能讓父親也變瘦，於是往上繼續。根若最後沒有鍵，它的唯一孩子變成新的根，樹變矮。
由上而下插入時先分裂，是為了讓「往上連鎖」不要發生。刪除的合併比較難完全避免連鎖，這是實作比插入容易出錯的原因。教學上先把第 5 節的插入做對，再實作刪除。
7. B+ 樹差在哪
B 樹的內部節點也放資料（或資料的指標）。B+ 樹把全部資料放在葉子，內部節點只放分隔鍵，用來路由。葉子再串成一條鏈。
後果：
- 範圍查詢沿著葉子鏈走，不用再中序走完整棵樹。資料庫的
BETWEEN與索引掃描用這個。 - 內部節點不放資料，一頁能放更多分隔鍵，樹更矮。
- 精確查詢一定走到葉子，即使內部曾經看過同一個鍵。分隔鍵可以是葉子鍵的複本。
檔案系統與多數關聯式資料庫的索引是 B+ 樹。演算法課上的插入分裂圖，用 B 樹畫比較清楚；工程上預設對方說的是 B+ 樹，除非對方指著節點裡的資料。
8. 複雜度
高度 (h) 滿足 (n \ge 1 + (t-1)\sum_{i=0}^{h-1} t^{i})，所以 (h = O(\log_t n))。
| 操作 | 節點讀寫次數 |
|---|---|
| 搜尋 | (O(\log_t n)) |
| 插入 | (O(\log_t n)) |
| 刪除 | (O(\log_t n)) |
CPU 比較次數還要再乘上節點內搜尋。磁碟模型不把這個當成主要成本。
9. 常見陷阱
- (t) 的定義不統一。 有人說「階是最大孩子數」，有人說「最小度 (t)」。寫程式前寫下「最多幾個鍵」。本篇最多 (2t-1) 個鍵。
- 分裂後中間鍵仍留在孩子裡。 B 樹的中間鍵上升後不留在孩子。B+ 樹的複本策略不同，不要混。
- 根也要求至少 (t-1) 個鍵。 根可以更瘦，否則空樹與單鍵樹不存在。
- 葉子不同層。 那是一般多路樹，高度保證沒了。
- 在記憶體裡用 B 樹取代
std::map。std::map是紅黑樹，快取行為已經針對指標節點調整。B 樹的收益來自分頁 I/O。
10. 練習題
- 接第 5 節的最後一棵樹，再插入
40。哪一個節點改變？樹會變高嗎？ - 若第 4 步不先分裂、硬把
6塞進[5, 10, 20]，違反了哪一條定義？ - 搜尋
7與搜尋15，分別經過哪些節點？ - B+ 樹為什麼較適合
SELECT * WHERE id BETWEEN 12 AND 30？ - (t=100)、(n=10^6) 時，樹高大約是幾層？和 (\log_2 10^6 \approx 20) 比，差在哪？
參考答案
40進入最右邊的[30]，變成[30, 40]。該節點只有 2 個鍵，未滿，根不變，樹不變高。- 節點會有 4 個鍵，超過 (2\cdot 2-1=3)。
7：根[10, 20]→ 左孩子[5, 6, 7]，找到。15：根 → 中間[12, 17]，沒有 15，也沒有更下一層，失敗。- 符合的鍵在葉子上是相鄰的，找到下界之後沿著葉子鏈掃描即可。B 樹的範圍結果散在內部節點與不同子樹，要做中序遍歷。
- (\log_{100} 10^6 = 3)。大約 3 到 4 層節點讀取，而不是約 20 次。前提是一次讀取真的拿到整個節點。
小結
B 樹用最小度 (t) 限制每個節點的鍵數，讓所有葉子同層，高度是 (\log_t n)。滿節點把中間鍵上升、左右拆開；根分裂是樹變高的唯一方式。B+ 樹把資料全放在葉子並串成鏈，範圍掃描才是資料庫索引的形狀。記憶體內的單鍵平衡樹仍然用紅黑樹或 AVL。