Write/Read/Space Amplification — B-Tree vs LSM Tradeoffs
Quantify WA/RA/SA; B-Tree lower cached RA vs LSM sequential writes + compaction WA; OLTP vs ingest.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
OLTP points vs ingest
Prefer
Name the dominant axis, then pick the engine
Hot point reads → B-Tree and a buffer pool that fits. High ingest → LSM and a compaction WA budget. Measure under your mix; defaults lie.
- B-Tree: low cached RA; page-granule WA; vacuum/fill-factor SA.
- LSM: sequential writes; compaction WA; multi-file RA until blooms/cache.
- Durable low latency is group commit — not an amp substitute.
Alternative
Quote 'LSM is always 10× WA' or 'B-Trees don't amplify'
Tiny in-place updates pay whole pages. Size-tiered LSM can look gentle on WA and brutal on RA/SA. Textbook 10× is a leveled-lifetime sketch, not a promise.
- SSD endurance tracks physical writes, not SQL row counts.
- Burst deletes inflate SA until compaction or vacuum.
- You can lower LSM WA by accepting higher RA/SA — explicit trade.
Three taxes on one 1KB put
Interview move: invent a 1KB value, then tax it on each axis.
- 1
Write amp
B-Tree: WAL + dirty leaf (8KB) + maybe split. LSM: WAL + flush + compaction rewrites across levels. - 2
Read amp
B-Tree: height pages cold, ~0–1 if hot. LSM: MemTable + several SSTables; blooms cut negatives. - 3
Space amp
B-Tree: fill factor + MVCC until vacuum. LSM: old versions until compact; leveled ~1.1× target, tiered worse. - 4
Pick knobs for the SLO
Buffer pool vs MemTable size, level ratio, vacuum lag, bloom bits — then measure.
Overview
Amplification quantifies storage-engine tax:
- Write amp (WA) = bytes written to disk ÷ logical bytes written.
- Read amp (RA) = pages/blocks read ÷ logical records returned.
- Space amp (SA) = physical bytes ÷ logical live bytes.
B-Trees usually win cached point-read amp but pay random write/split costs. LSMs sequentialize writes but pay compaction write amp and multi-level read amp. Choose by workload shape.
Senior prompts: "Why is disk IO 10× user traffic?" or "SSD dying early?" → write amplification. "p99 gets after ingest?" → read amp / compaction. "Disk 4× data size?" → space amp (versions, fragmentation, tombstones). Naming the triangle and giving numeric sketches separates strong candidates.
Definitions with tiny examples
Suppose the user writes a 1 KB value once.
Write amplification
- B-Tree sketch: WAL (~1KB) + dirty leaf page flush (8KB) + possible split (2×8KB) + parent → WA easily ≫ 1. Page granularity dominates small values. Mechanics: B-Tree internals.
- LSM sketch: WAL + flush (~1KB sorted) + compaction rewriting the key across levels (leveled factor ~10 times over lifetime in textbook models) → WA often 10–30× depending on config. Mechanics: LSM.
Read amplification
- B-Tree: height (e.g. 3) page reads when cold; ~0–1 if hot in the buffer pool.
- LSM: check MemTable + several SSTables/levels (blooms reduce); worst case many overlapping files in L0.
Space amplification
- B-Tree: page fill factor (often ~50–70% after splits) + MVCC dead tuples until vacuum.
- LSM: old versions until compacted; leveled targets ~1.1×; size-tiered can be much worse transiently.
When to choose which
| Workload | Prefer | Why |
|---|---|---|
| OLTP point reads, modest writes | B-Tree | Low RA when cached; predictable pages |
| High ingest / telemetry / TSDB | LSM | Sequential WA pattern; cheaper bulk write |
| Heavy updates in-place | Depends | B-Tree update-in-place vs LSM new versions + compaction |
| Strict durable low latency | Either + group commit | Amp ≠ fsync policy — fsync |
| Range scans | B+Tree leaves or well-leveled LSM | Avoid size-tiered with huge overlap |
Recap
- B-Tree: pros RA for hot points; cons random writes, split WA, vacuum.
- LSM: pros sequential writes, ingest; cons compaction WA, RA without blooms/cache, space until GC.
Amplification triangle
Flow
- 1
1. Write amp: WAL + pages or compaction
- next4. Pick engine and knobs for the dominant SLO
- 2
2. Read amp: tree height or LSM levels
- next4. Pick engine and knobs for the dominant SLO
- 3
3. Space amp: fill factor or versions
- next4. Pick engine and knobs for the dominant SLO
- 4
4. Pick engine and knobs for the dominant SLO
Lesson map
Write/Read/Space Amplification — B-Tree vs LSM Tradeoffs
Quantify WA/RA/SA; B-Tree lower cached RA vs LSM sequential writes + compaction WA; OLTP vs ingest.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB w["1. Write amp: WAL + pages or compaction"] r["2. Read amp: tree height or LSM levels"] s["3. Space amp: fill factor or versions"] c["4. Pick engine and knobs for the dominant SLO"] w -->|1. Write amp: WAL + pages or compaction| c r -->|2. Read amp: tree height or LSM levels| c s -->|3. Space amp: fill factor or versions| c
Sandbox: amplification counters (Python)
Illustrative counters — not a real engine.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Decision helper (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Interview Q&A
Define write amplification crisply.
Answer
Physical bytes written to storage divided by logical bytes the application intended to write.
Why can B-Tree WA be high for tiny updates?
Answer
Whole pages are the write granule. WAL + page flush + splits dwarf a 64-byte column change.
Why do LSM textbooks cite ~O(level_ratio) WA?
Answer
Each key may be rewritten each time it is compacted into the next larger level (leveled). That is a lifetime sketch, not a constant.
How do blooms change RA?
Answer
They cut negative lookups and reduce SSTables probed — RA drops without changing WA much.
Space amp after burst deletes?
Answer
Tombstones/versions linger → SA up until compaction or vacuum. Queries may also slow (RA).
SSD endurance link?
Answer
High WA burns NAND P/E cycles. LSM compaction and B-Tree page churn both matter. "The SSD died" is often an amp incident.
Can you lower LSM WA?
Answer
Larger MemTables, tiered compaction, fewer levels — and you accept higher RA/SA. Explicit trade, not a free knob.
Interview one-liner comparing engines?
Answer
"B-Trees optimize update-in-place reads; LSMs optimize sequential writes — pick from the amp triangle against SLOs."
Pitfalls
On a whiteboard: 64-byte column change on an 8KB B-Tree leaf vs the same put compacted through 4 LSM levels at 10×. Compute a back-of-envelope WA. Then say which workload still prefers each engine.