Storage engines — B-trees vs LSM-trees, WAL, memtables, SSTables
What Postgres's engine actually does for you — the machinery beneath every query you wrote.
Concept → your projects
Two dominant write-optimized/read-optimized designs:
B-tree (Postgres/InnoDB): sorted pages in a balanced tree. Writes: in-place page updates + WAL records; page splits on overflow. Reads: O(log N) point lookups, great range scans. Write cost: random page writes (mitigated by shared buffers + WAL-first). Best when: read-heavy, point/range queries, updates in place.
LSM-tree (RocksDB/Cassandra/LevelDB): writes go to an in-memory memtable + WAL, flush to immutable SSTable files; reads check memtable → levels of SSTables (Bloom filters skip files); compaction merges levels, reclaiming space and deleted tombstones. Write cost: sequential appends (why LSM wins write throughput); read cost: multi-level checks (why B-trees win reads); write amplification reappears as compaction (levels rewrite data repeatedly), read amplification on misses, space amplification until compaction. Tiering vs leveling: size-tiered (cheaper writes, more space), leveled (better reads, more rewrite).
The WAL everywhere principle: both designs log before touching data — Postgres's WAL and LSM's memtable-WAL are the same idea (Day 33): sequential durability, lazy structural change.
Postgres specifics you should know beneath your queries:
- Heap tables: rows appended wherever space exists (not clustered by key — unlike MySQL's clustered PK index); indexes point to heap via ctid. Consequence: index scan = index pages + random heap fetch (why Index Only Scan is special — visibility map permitting).
- Updates are appends: MVCC writes a new row version (Day 31) — Postgres is more log-structured than people think; VACUUM is its compaction.
UPDATE ... SET status='ACTIVE'= new tuple + dead tuple + WAL — your conditional updates literally create garbage that autovacuum reclaims. This analogy (VACUUM ≈ compaction, dead tuples ≈ tombstones) is a great interview bridge. - CLUSTER/pkey index: physical reordering exists but is one-shot; fillfactor controls page headroom for in-place updates.
Where your systems sit, honestly: you operate Postgres's engine, not your own — but the concepts explain your operational surface: long transactions pin dead tuples → bloat (the "vacuum can't clean" incidents), heavy index counts slow your writes (write amplification), synchronous_commit is the WAL fsync knob. RocksDB-in- anger would matter if you ran Kafka (LogSegment + indexes) or Cassandra.
The Bitcask model (the minimal log-structured KV from your topic list, worth one paragraph): a directory of append-only files; PUT appends key→file/offset/value, DELETE appends tombstone; GET reads an in-memory keydir → one disk read; merge rewrites live data. It's Redis-durability minus RAM, the simplest possible engine with real durability — and zoth's outbox_events table is conceptually a Bitcask: append-only writes, a "keydir" (the partial index of unpublished rows), and "compaction" (marking published = merge). Seeing that rhyme is the sign the concepts landed.
Bulletproof your resume
Say these answers aloud before moving on
These are the follow-ups an interviewer will actually ask about your projects.
Why do LSM-trees write faster than B-trees, and what do they pay?
Writes become sequential appends (memtable WAL + immutable SSTable flushes) instead of random in-place page updates. Payment: reads check multiple levels (read amplification — Bloom filters mitigate), deleted/overwritten data lingers until compaction (space amplification), and compaction itself rewrites data repeatedly (write amplification, ironically). The sweet spot is write-heavy workloads with bounded read-latency requirements; B-trees win read-heavy point-lookup workloads like my access-request state machine.
How is Postgres MVCC similar to an LSM?
Both never modify in place: an UPDATE writes a new version (MVCC) or appends a new record (LSM), and old/dead data is reclaimed by a background process (VACUUM vs compaction) with tombstone-like hazards — a delete leaves a dead tuple until vacuum, just as an LSM delete is a tombstone until compaction. The operational lesson is identical: monitor the reclaimer, don't block it (long transactions pin dead tuples the way long readers pin SSTables), and expect write cost to exceed the logical change.
What would make you move a table off Postgres's heap/B-tree?
When the access pattern stops matching the engine: append-only, write-dominated, keyed lookups over billions of rows (LSM wins: e.g., Discord's message store → ScyllaDB); or wide scans of billions of rows for analytics (columnar wins). My workloads are relational, read-mostly after write, join-heavy — none of the triggers. I'd also note the intermediate step: Postgres partitioning + BRIN indexes handle time-series append patterns before an engine change is justified.