🎯 什麼情境該想到我
當你在選資料庫/儲存引擎，或想理解「為什麼某個 DB 寫很快但讀較慢（或相反）」時。
⚙️ 怎麼用（依讀寫特性選）
- B-Tree（就地更新）：資料原地排序更新，讀優化、範圍查詢好；寫入需隨機 I/O。傳統關聯式 DB（MySQL InnoDB…）。
- LSM-Tree（追加寫）：寫入先進記憶體，再批次刷成不可變的 SSTable，背景合併（compaction）。寫優化、順序 I/O 快；讀要查多層 + 靠 Bloom filter 加速。RocksDB、Cassandra、LevelDB…
- 用「三種放大」判斷取捨：讀放大、寫放大、空間放大——沒有引擎三者全贏。寫重 → LSM；讀重/範圍查多 → B-Tree。
★ 核心對照（這張表就是全部）
| B-Tree（PG、MySQL InnoDB、SQLite） | LSM-Tree（RocksDB、Cassandra、LevelDB） | |
|---|---|---|
| 寫入 | ★ 原地更新：找到頁 → 改 → 寫回（隨機寫） | ★ 只追加：寫 memtable → 滿了就刷成 SSTable（順序寫） |
| 寫入吞吐 | 中 | ★ 高（順序寫快得多） |
| 讀取 | ★ 可預測： 次 I/O，走一條路徑 | ⚠️ 可能查多層（memtable → L0 → L1 → …） |
| 寫入放大 | 中（頁分裂、WAL 寫兩次） | ★ 高（compaction 反覆重寫同樣的資料） |
| 空間放大 | 中（頁內碎片，約 60–70% 填充率） | ★ 低（壓縮率好）但 compaction 前會暫時翻倍 |
| 範圍掃描 | ★ 好（葉節點有序且鏈結） | 中（要合併多層） |
| 刪除 | 就地標記 | ★ 寫一個 tombstone（墓碑）——空間之後才回收 |
| 延遲穩定性 | ★ 穩定 | ⚠️ compaction 會造成尾延遲尖峰 |
★ 三種「放大」（理解儲存引擎的核心概念）
| 放大 | 定義 | 誰嚴重 |
|---|---|---|
| 寫入放大 | 實際寫到磁碟的位元組 ÷ 應用寫入的位元組 | ★ LSM（compaction 把同一筆資料重寫很多次） |
| 讀取放大 | 一次查詢要讀幾次磁碟 | ★ LSM（要查多層） |
| 空間放大 | 實際佔用 ÷ 有效資料 | ★ B-Tree（頁未填滿）；LSM 在 compaction 時暫時很高 |
★ RUM 猜想：Read、Update、Memory 三者最多只能優化兩個。
這就是為什麼沒有「全面更好」的儲存引擎——每一個都是在這個三角上選了一個位置。
★ LSM 的讀取怎麼救
查一個 key：
① memtable（記憶體，快）
② ★ Bloom filter 判斷「這個 SSTable 可能有嗎」
→ 說「沒有」就是真的沒有（不會偽陰性），直接跳過，不用讀磁碟
③ 真的可能有才讀 SSTable
★ Bloom filter 是 LSM 讀取效能的關鍵。沒有它，每次讀都要查所有層。
（它有偽陽性但沒有偽陰性——這個不對稱正是它有用的原因。）
★ Compaction：LSM 的命脈，也是它的痛點
| 策略 | 做法 | 取捨 |
|---|---|---|
| Size-tiered | 同樣大小的 SSTable 合併成更大的 | ★ 寫入放大低，空間放大高（同一筆資料存在多層） |
| Leveled | 每層大小固定倍增，層內 key 不重疊 | ★ 讀取與空間好，寫入放大高 |
| 混合 / 時間序列專用 | Cassandra 的 TWCS（依時間窗） | 時序資料專用 |
★ Compaction 是背景 I/O，會和前台查詢搶資源 →
這就是 LSM 尾延遲不穩定的根源。 生產上要限制 compaction 的頻寬。
★ 實務上什麼時候該在意這件事
多數時候不用在意——你不會因為儲存引擎而選資料庫。但這幾個情況要：
| 情況 | 影響 |
|---|---|
| 寫入吞吐是瓶頸（日誌、遙測、IoT、事件流） | ★ LSM 明顯有利 |
| 需要穩定的 p99 讀取延遲 | ★ B-Tree（LSM 的 compaction 會製造尖峰） |
| 大量範圍掃描 / 分析查詢 | B-Tree 或列式儲存 |
| ★ 寫入模式是「大量刪除或覆寫」 | ⚠️ LSM 的 tombstone 會累積；Cassandra 的「墓碑地獄」是經典問題 |
| SSD 壽命敏感（寫入放大 = 磨損） | 要算寫入放大 |
★ 一個實用的觀察：
PostgreSQL 的 MVCC 讓 UPDATE 實際上是「寫新版本 + 標記舊版本」——
行為上有點像 LSM（所以需要 VACUUM 來回收，就像 compaction）。
★ PG 的表膨脹（bloat）與 autovacuum 調校，本質上就是 compaction 的問題。
其他儲存形態
| 形態 | 適合 |
|---|---|
| 列式（columnar） | ★ 分析查詢（只讀需要的欄、壓縮率極高）——ClickHouse、Parquet |
| 雜湊索引 | 只需要點查、資料能放記憶體（見 雜湊表） |
| B+Tree vs B-Tree | ★ B+Tree 只在葉節點存資料且葉節點互相鏈結 → 範圍掃描快得多，實務上都是 B+Tree |
🧪 我實際套用的紀錄
- 2026-07-15：（待填）
⚠️ 注意 / 什麼時候不適用
- ★ 不要為了儲存引擎換資料庫。生態、運維成熟度、團隊熟悉度的權重遠高於此。
這個知識的用途是「解釋為什麼我的寫入會慢 / p99 會抖」，不是選型的第一準則。 - ★ LSM 的 tombstone 會咬人。大量刪除後空間不會立刻回收，而且讀取時要掃過墓碑。
Cassandra 的gc_grace_seconds與墓碑閾值是必須理解的營運參數。 - ★ PG 的 autovacuum 調校是同一類問題。高更新率的表會膨脹 → 查詢變慢 → 要調 vacuum 的積極度。
- B-Tree 的頁分裂在隨機 key 插入時最嚴重。★ 用遞增的主鍵（如 UUID v7 而非 v4）可以大幅減少分裂與隨機 I/O。
- 索引不是免費的。每個索引都要在寫入時更新 → 寫入放大乘以索引數量。
- 量測的是「你的工作負載」。benchmark 數字與你的讀寫比、key 分布、資料大小高度相關。
- 雲端資料庫的儲存層可能完全不同（Aurora 把 log 直接寫進分散式儲存），上面的模型不完全適用。
🔗 相關工具
- 工具-預寫日誌與崩潰復原 —— 兩種引擎都靠它保證持久性
- 紅黑樹 —— B-Tree 的對照：為什麼磁碟上要用高扇出的樹
- 雜湊表 —— 另一種索引形態
- 工具-用trigram索引加速模糊查詢 —— 特殊索引型別
- 工具-資料分區 —— 更上層的擴展手段
- 工具-快取與資源優化 —— 比換引擎便宜得多
- 工具-程式碼調校 —— 先量再選
- 資料庫底層原理、設計資料密集型應用