How a Storage Engine Actually Works: LSM vs B-tree

Most engineers treat the storage engine as a black box: data goes in, queries come out. But the two families of engine underneath every OLTP database make opposite bets, and knowing which — and how they work — is what lets you choose and tune one. So I built a miniature LSM engine from scratch (memtable, WAL, sorted SSTables, Bloom filters, compaction, tombstones) and measured the mechanics.

Runnable companion: lsm-vs-btree on GitHub. make internals && make bloom && make index reproduces every number below (pure Python).

Two bets on the same problem

Every engine must serve fast writes and fast reads from disk, and can't fully optimize both:

• Log-structured (LSM-tree) — never overwrite in place. Buffer writes in an in-memory memtable (with a write-ahead log for durability); when it fills, flush an immutable, sorted SSTable. Merge SSTables periodically (compaction). Sequential writes → high write throughput. Powers Cassandra, RocksDB, ScyllaDB, LevelDB.
• Update-in-place (B-tree) — modify the page where the key lives. Stable, low-latency reads; more random write I/O. The default in PostgreSQL, MySQL/InnoDB, SQLite.

Not "better" — a workload bet. Here's what the mechanics look like measured.

LSM mechanics

Write amplification: 30,000 writes over 10,000 keys → 10.1x bytes written per live byte

Read amplification:
  10 un-compacted SSTables → one lookup reads all 10 files
  after compaction (1 SSTable) → 1 read

Tombstone delete:
  get(key) after delete       → None  (masked by a tombstone)
  get(key) after compaction   → None  (tombstone dropped, space reclaimed)

The whole LSM tension is here. Compaction rewrites data (write amplification — the price, and a cause of SSD wear) to keep the file count small, which keeps read amplification low. And a delete is a write: a tombstone that masks the key, with the real data lingering until compaction — which interacts directly with GDPR/erasure timelines and space reclamation.

The Bloom filter, measured

10,000 keys across 20 SSTables; 2,000 lookups for keys that don't exist:

                       SSTable reads    per lookup
  without Bloom filter        40,000          20.0
  with Bloom filter              424           0.21

A lookup for a missing key would, unaided, read every SSTable to be sure it's absent. Each SSTable's Bloom filter answers "definitely not here" from memory, so the read is skipped — 94x fewer disk reads. This is why every serious LSM ships Bloom filters, and why their size is a tuning knob (bigger filter → fewer false positives → fewer wasted reads, at the cost of memory).

The index trade-off

Indexes get added by reflex. On a real B-tree (SQLite, 200k rows, a filtered COUNT):

metric                            no index    with index
query latency (median)             7.21 ms       0.01 ms
insert throughput             1,073,845/s    221,499/s
on-disk size                        6.4 MB        9.2 MB

The index made the read ~1048x faster, made inserts ~4.8x slower, and grew the database 45%. An index is a secondary B-tree the engine keeps up to date on every write — read speed bought with write cost and space. Index by query pattern, not by reflex.

What I'd say in an interview

• LSM vs B-tree is a workload bet. Write-heavy / high-ingest leans LSM; read-heavy / latency-sensitive OLTP leans B-tree. Benchmark the real workload; don't assume.
• Compaction trades write amplification for read amplification — the LSM knob; Bloom-filter size and compaction strategy are how you tune it.
• Deletes are lazy in an LSM (tombstones) — plan space reclamation and compliance timelines.
• Every index is read-speed bought with write cost and space — index the hot query, not every column.
• Knowing the mechanics (memtable, compaction, Bloom filter, WAL) is what turns tuning from guesswork into prediction.