Database Storage Engines — WAL, B-Trees & LSM Trees
Storage engine = on-disk layout + recovery; B-Tree vs LSM families share a WAL durability spine; pick by write:read, latency SLO, and vacuum/compaction ops cost.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Update-in-place pages vs sequential ingest
Prefer
Match the family to the mix, not the brand
Postgres/InnoDB win hot point-read OLTP. RocksDB/Cassandra win sustained ingest. Both still force a WAL before they will call a commit durable.
- B-Tree: low cached read amp; random dirty flushes; vacuum/purge as the tax.
- LSM: sequential writes; compaction write amp; multi-level read amp.
- WiredTiger (MongoDB) can do either — the engine is pluggable, the triangle is not.
Alternative
Pick Cassandra because writes are 'fast', or Postgres because SQL is familiar
Brand names hide the I/O. Interviews want write:read, p99 durable commit, and who pays for vacuum vs compaction at 3am.
- In-memory only is not durable without a WAL or equivalent replication story.
- Hash indexes do not replace a storage engine — they skip range scans.
- Tight durable commit latency is an fsync/group-commit problem in either family.
What happens to one INSERT
Same five beats on both families. The fork is where the bytes live after the WAL append.
- 1
Logical record arrives
INSERT / UPDATE / DELETE. SQL is done; the engine owns layout. - 2
Assign LSN, append WAL
Must reach durable media per sync policy before a durable ack. Depth: WAL lesson. - 3
Update memory
B-Tree: dirty the buffer-pool page. LSM: insert the MemTable. - 4
Flush later
Pages or SSTables go out asynchronously. Checkpoints advance the recoverable frontier. - 5
Crash → REDO
Replay from last checkpoint. ARIES-style engines also UNDO loser txns.
Overview
A storage engine is how a database lays out durable state on disk and comes back consistent after a crash. Two families dominate production:
- Update-in-place B-Trees — Postgres heap + indexes, InnoDB, WiredTiger B-Tree.
- Append-friendly LSM trees — RocksDB, LevelDB, Cassandra/Scylla, WiredTiger LSM.
Both share a durability spine: write a WAL / redo log before mutating data pages. Senior interviews almost always ask "why Postgres vs Cassandra?" or "what happens when power fails mid-write?" The answer is storage-engine shaped — write:read ratio, latency SLO, compaction/vacuum cost, and recovery time. Production outages more often come from WAL sync policy, buffer-pool thrashing, or compaction backlog than from SQL syntax.
You should be able to:
- Separate the SQL layer from the engine.
- Sketch WAL → memory → async flush → checkpoint → REDO.
- Map a workload to B-Tree vs LSM without hiding behind a product name.
Two families
| Approach | Pros | Cons |
|---|---|---|
| B-Tree update-in-place | Low read amp for cached point lookups; familiar vacuum/checkpoint ops | Random writes; page-split write amp; vacuum/purge cost |
| LSM append | Sequential writes; high ingest throughput | Compaction write amp; multi-level read amp; space amp from versions |
| In-memory only | Lowest latency | Not durable without WAL/replication |
| Hash indexes only | Fast equality | No range scans; poor as the whole table organization at scale |
Rule of thumb: engines trade write amp vs read amp vs space amp. Interviews want you to name that triangle and map it to SLOs. Numbers live in amplification.
B-Tree pages are the I/O unit; which index access method sits on those pages (B-tree vs hash vs GIN vs GiST) is a different question — index types. Checkpoint is not vacuum: VACUUM / wraparound reclaims dead MVCC versions; a checkpoint advances recovery start.
Architecture map
Decisions
- 1
1. Client write
- next2. WAL append + sync policy
- 2
2. WAL append + sync policy
- next3. Engine family?
- ?
3. Engine family?
- B-Tree4a. Buffer pool dirty pages
- LSM4b. MemTable then flush SSTable
- 4
4a. Buffer pool dirty pages
- next5a. Checkpoint / page flush
- 5
4b. MemTable then flush SSTable
- next5b. Compaction across levels
- 6
5a. Checkpoint / page flush
- next6. Crash: REDO from checkpoint
- 7
5b. Compaction across levels
- next6. Crash: REDO from checkpoint
- 8
6. Crash: REDO from checkpoint
- next7. Durable consistent state
- 9
7. Durable consistent state
Lesson map
Database Storage Engines — WAL, B-Trees & LSM Trees
Storage engine = on-disk layout + recovery; B-Tree vs LSM families share a WAL durability spine; pick by write:read, latency SLO, and vacuum/compaction ops cost.
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 a["1. Client write"] b["2. WAL append + sync policy"] c["3. Engine family?"] d["4a. Buffer pool dirty"] a -->|1. Client write to 2. WAL append + sync policy| b b -->|2. WAL append + sync policy| c c -->|B-Tree| d
Interview framing — pick by workload
- High point-read OLTP, modest writes → B-Tree (Postgres / InnoDB).
- High ingest, telemetry, time-series, write-heavy → LSM (RocksDB / Cassandra).
- Mixed with a strict durable commit latency → watch fsync / group commit in either family.
What fails first under a write spike: B-Tree dirty-page flush / WAL sync latency; LSM compaction debt and stall. Name the symptom, not just "disk full".
Sandbox: tiny engine classifier (Python)
Educational workload → family hint. Not a production picker.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Same hint (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Interview Q&A
What is a storage engine vs the SQL layer?
Answer
SQL parses, plans, and optimizes. The storage engine owns on-disk layout, buffering, WAL, indexes, and crash recovery. Same SQL can sit on different engines (MySQL InnoDB vs MyISAM historically; MongoDB WiredTiger B-Tree vs LSM).
Why do almost all durable engines have a WAL?
Answer
Data-page writes are random and can be incomplete on crash (torn pages). Appending a sequential log first gives a single ordered history to REDO. Depth: WAL.
When would you pick LSM over B-Tree?
Answer
Sustained high ingest, write-heavy telemetry, wide rows that would thrash B-Tree pages — and you can tolerate compaction CPU/IO plus slightly higher read amp. Details: LSM.
What is write amplification?
Answer
Bytes written to storage ÷ logical bytes the user wrote. Page splits, WAL+data, and LSM compaction all inflate it. Triangle: amplification.
How does WiredTiger fit?
Answer
MongoDB's engine supports B-Tree-like and LSM options. Interviews like that you know engines are pluggable and the tradeoffs move with config, not with the logo.
Checkpoint vs vacuum — same thing?
Answer
No. Checkpoint advances recovery start (flush dirty state / note an LSN). Vacuum/purge reclaims dead MVCC versions — related ops cost, different job. Cousin: VACUUM / wraparound.
What fails first under write spikes?
Answer
B-Tree: dirty-page flush / WAL sync latency. LSM: compaction debt and stall. Name the symptom, not just "disk full".
How do you explain Postgres storage in one minute?
Answer
Heap pages + B-Tree indexes, shared_buffers cache, WAL before durable commit, checkpoints flush dirty pages; vacuum cleans dead tuples. Index AM choice is extra: B-tree / hash / GIN / GiST.
Pitfalls
Whiteboard three workloads: (1) checkout OLTP, 20k point reads/s, 2k writes/s, 10ms durable p99; (2) telemetry ingest, 500k writes/s, rare point reads, 50ms durable p99; (3) mixed with a 2ms durable-commit SLO. For each, name B-Tree vs LSM vs "either + group commit", and which sibling page you would open next.