各種 B-Tree 變體共享同一套骨架（樹結構、split/merge 平衡、查找演算法），差別在並行控制、磁碟頁面表示、維護流程。它們幾乎都在回答同一個問題：就地更新 B-Tree 的哪個痛點——寫放大、並發、SSD 隨機寫——最該先解？
🧠 Intuition
TIP
原始 B-Tree 在旋轉磁碟上很好，但在 SSD 上主要吃兩個虧：頁面重寫帶來的寫放大，以及預留插入空間帶來的空間開銷。各變體就是針對其中一項（或兩項）動刀。
- 不就地改，改成寫新的：Copy-on-Write 把頁面當不可變，改動時複製出新頁、原子換掉根指標——換來讀者免同步。
- 先緩衝、晚傳播：Lazy B-Tree（WiredTiger、LA-Tree）把更新先塞進 buffer，減少對同一節點的重複 I/O。
- 借 log-structured 手法：FD-Tree、Bw-Tree 把小型隨機寫攢成大寫、寫進不可變 run 或 append-only 鏈，正面對付 SSD 隨機寫與寫放大。
- 不必知道頁大小也近最佳：Cache-Oblivious B-Tree 不需底層記憶體階層參數就能給出漸近最優效能。
⚖️ Tradeoffs
Copy-on-Write B-Tree — 不改舊頁，複製出新樹再換根指標
- 修改頁面時先複製其內容、在副本上改，建立一條平行的樹階層，最後原子性地更新指向頂層頁面的指標；未改動的頁面被重用。
- 最大優勢：讀者不需要任何同步機制，已寫入的頁面不可變，可無 latch 存取，也不會被寫入者阻塞。
- LMDB（Lightning Memory-Mapped Database）是代表：透過 memory map 直接讀寫，因此不需要 page cache、WAL、checkpointing 或 compaction；只保留根節點的兩個版本，且因 append-only 設計不用 sibling pointer。
- 缺點：需要更多空間（舊版本雖只留短暫時間）與處理器時間（複製整頁）；但 B-Tree 通常較淺，簡潔性多半能彌補。
Lazy B-Tree — 把更新緩衝在節點上，延遲傳播降 I/O
- 用更輕量、並行友善的記憶體結構緩衝更新，減少後續對同一節點的 I/O，並延遲傳播。
- WiredTiger（MongoDB 現行預設引擎）：clean page 僅由索引構成，更新先進 update buffer；讀取時 buffer 與磁碟頁內容合併回傳最新值，flush 時經 reconciliation 調和後持久化；buffer 用 skiplist，複雜度近搜尋樹但並行更好。頁面更新與 split/merge 交給背景執行緒，讀寫路徑不必等。
- LA-Tree（Lazy-Adaptive Tree）：不緩衝個別節點，而是把節點分組成子樹、每個子樹掛一個 buffer；更新先進根 buffer，滿了就 cascaded 往下層傳播，直到葉節點才一次套用整批 insert/update/delete。
FD-Tree — 用 log-structured 把隨機寫關進小 B-Tree
- 緩衝的目的是避免大量小型隨機寫，改成單一較大寫入。FD-Tree（Flash Disk Tree）為此設計。
- 結構：一個小型可變的 head tree（小 B-Tree）+ 多個不可變的排序 run；隨機寫 I/O 被限制在 head tree 內，填滿後轉入不可變 run，run 超過閾值再與下一層合併——流程與 LSM 的 compaction 非常類似。
- fractional cascading：在相鄰層的排序陣列間建 bridge（從低層 pull 元素到高層），最高層做二元搜尋後，下層搜尋空間大幅縮小，藉此串接多個 run、降低搜尋成本。
- 不就地更新：同一 key 出現在多層時用 tombstone（論文稱 filter entry）標記刪除，傳播到最低層即可丟棄。
Bw-Tree — append-only delta 鏈 + mapping table，做到 lock-free
- 針對就地更新最大的問題「寫放大」，走完全不同的路：把 base node 與其修改分開寫，修改（delta node）串成一條鏈（新→舊→base），每次更新單獨儲存、不重寫既有節點。
- 節點是邏輯而非物理實體：不必預先配置空間、不要求固定大小、不需連續記憶體。
- 用記憶體中的 mapping table 把邏輯識別符對應到磁碟實際位置，並以單一 compare-and-swap 更新偏移量——藉此消除 latch、使樹 lock-free。
- 仍需 split/merge（SMO）處理 overflow/underflow；delta 鏈過長時做 consolidation 重建節點，並用 epoch-based reclamation 安全回收垃圾。
Cache-Oblivious B-Tree — 不知道 page 大小仍近最佳
- block 大小、節點大小、cache line 對齊都會影響 B-Tree 效能。Cache-oblivious 結構不需知道底層記憶體階層參數，即可提供漸近最優效能——用兩層記憶體模型推理，卻享有多層階層的效益。
- 由靜態 B-Tree + packed array 組成。靜態樹用 van Emde Boas layout 建構：在邊的中間層切分並遞迴，使任何遞迴子樹都落在連續記憶體區塊中。
- 動態操作靠 packed array：連續儲存但保留間隙供插入，插入時重定位較少；太密或太稀疏時重建以調整大小，靜態樹作為其索引隨之更新。
🔑 Takeaways
- 各變體本質是回答「先解哪個痛點」：寫放大、並發、SSD 隨機寫、空間開銷。
- **Copy-on-Write（LMDB）**用不可變頁 + 原子換根指標，讓讀者免同步，代價是空間與複製成本。
- Lazy B-Tree（WiredTiger、LA-Tree）靠緩衝更新降寫放大；FD-Tree 用不可變排序 run 降空間開銷；Bw-Tree 用 append-only + mapping table + CAS 同時兼顧兩者並做到 lock-free。
- Cache-Oblivious B-Tree 用 van Emde Boas layout + packed array，不需 page 大小參數也能近最佳。
No notes yet — jot your takeaways or Q&A here.