兩種主流儲存引擎家族。B-Tree 就地更新（讀快、寫放大高）；LSM-Tree 只追加（寫快、讀要合併多層）。選哪個，本質是在問這個負載「讀重還是寫重」。
🧠 Intuition
TIP
一句話分辨：B-Tree 是「改一頁就回去改那一頁」；LSM 是「先記在記憶體，滿了就傾倒成新檔，之後背景再慢慢合併」。前者犧牲寫、後者犧牲讀，再各自用手段把弱項補回來。
- B-Tree：固定大小的頁（page）組成平衡樹，每筆 key 在樹上只有一個位置；更新 = 找到頁、就地覆寫。為了崩潰安全，先寫 WAL（redo log）。
- LSM-Tree：寫入先進記憶體的 memtable（有序結構），滿了就 flush 成不可變的 SSTable；背景 compaction 把多個 SSTable 合併、丟掉被覆蓋與刪除（tombstone）的 key。
⚖️ Tradeoffs
寫放大 (Write Amplification)
- B-Tree：一次邏輯寫 → WAL 一次 + 頁本身改寫一次（頁分裂時更多）。
- LSM：一筆資料一生中會被 compaction 重寫多次（每下沉一層重寫一次）。
- 結論：兩者都有寫放大，但來源不同；LSM 的放大更可被「順序寫」攤平。
寫吞吐 — LSM 通常勝
- LSM 把隨機寫轉成順序寫（memtable 排序 + 順序 flush），對 SSD/HDD 都友善。
- B-Tree 的就地更新是隨機 I/O，且頁分裂會放大。
- 寫重負載（時序、日誌、計數器）多選 LSM：LevelDB / RocksDB / Cassandra / HBase。
讀延遲 — B-Tree 較穩
- B-Tree 讀一筆 = O(log n) 次頁存取，路徑固定、延遲可預測。
- LSM 讀一筆可能要查 memtable + 多個 SSTable，靠 Bloom filter 跳過不含此 key 的檔案來救。
- 讀重、要穩定 p99 的負載（OLTP）多選 B-Tree：PostgreSQL / MySQL InnoDB。
空間 — LSM 較省，但有暫時膨脹
- LSM 的 SSTable 緊密排列、可壓縮，碎片少。
- B-Tree 的頁通常留有空隙（為了未來插入），且分裂留下碎片。
- 但 LSM 在 compaction 進行中會同時存在新舊檔，瞬時佔用上升。
🔑 Takeaways
- 寫重選 LSM，讀重選 B-Tree——這是第一刀。
- LSM 用 memtable + 順序 flush 換寫吞吐，用 Bloom filter + compaction 補讀放大。
- B-Tree 用就地更新換穩定讀延遲，用 WAL 補崩潰安全，代價是隨機寫與頁碎片。
- 兩者都有寫放大，差別在「能不能轉成順序 I/O」。
2026-07-01
- Q: 為什麼 LSM 寫快卻不會「越寫越慢」？
- A: 關鍵在 compaction 是背景進行，把寫入路徑與整理路徑解耦。但若寫入速度長期超過 compaction 速度，SSTable 會堆積、讀放大上升，這就是 LSM 要監控的「compaction 跟不上」風險。