Storage engines: B-trees vs LSM-trees

Why this matters

When someone asks you "which database should we use?", the honest answer almost always traces back to the storage engine. Postgres feels fast and predictable but eats CPU during maintenance — that's because of its B-tree + MVCC design. Cassandra ingests writes at insane rates but reads have variable latency — that's because of its LSM-tree design. You can't reason about these systems' behaviour, tune them, or pick between them without understanding what's happening on disk.

Every database stores its data in some structure on disk. The choice of structure determines:

• How fast writes are
• How fast reads are
• How much disk space you waste
• How predictable latency is (any background process competing for I/O can cause stalls)
• What the operational pain looks like (vacuum, compaction, etc.)

From first principles: what does a storage engine need to do?

At its simplest, a storage engine needs to:

1. Take a key-value pair and put it on disk durably (survives a crash).
2. Look up a key efficiently (better than linear scan).
3. Support range queries (give me all keys between X and Y).
4. Reclaim space when keys are deleted or updated.
5. Stay correct under concurrent reads and writes.

The naive approach — "write everything to one file in insertion order" — fails (5) because there's no order to look things up by. The "put everything in one sorted file" approach fails because every insert requires rewriting the file. Real storage engines balance these competing demands.

The fundamental tradeoff: three amplifications

"Amplification" is the ratio of actual work the database does to the logical work you asked it to do. The database multiplies your operation into more underlying work — and it's almost always more than you'd guess.

1. Write amplification — "I write 1 byte; how many bytes hit disk?"

You issue INSERT INTO accounts (balance) VALUES (100) — that's logically writing maybe 50 bytes (the row).

What actually happens:

• WAL record written first: ~100 bytes
• Page that contains the row: 8 KB written (you can't write half a page — pages are atomic)
• If the page splits: another 8 KB for the new page + 8 KB for the parent update
• Eventually, the dirty page is flushed to disk in a checkpoint

So you wrote 50 bytes logically; the disk saw ~16-24 KB of actual writes. That's write amplification of ~300× for a worst-case insert. Steady-state is typically 10–20× because most inserts don't cause splits.

Why you care:

• SSDs have finite write endurance. Each cell can be written ~3,000–100,000 times before it dies. High write amplification = SSD wear-out faster than you planned.
• Writes consume I/O bandwidth that's then unavailable for reads — so high write amp can starve reads.

For LSM-trees, write amp is even higher because of compaction: the same key gets rewritten multiple times as it's merged through levels. RocksDB leveled compaction = ~10–30× write amp under good workloads; can hit 100× under bad ones.

2. Read amplification — "I read 1 row; how many disk pages were touched?"

You issue SELECT balance FROM accounts WHERE id = 42 — logically reading one row.

What actually happens in a B-tree:

• Read root page (8 KB) → walk to branch
• Read branch page (8 KB) → walk to leaf
• Read leaf page (8 KB) → find row

That's 3 page reads = 24 KB read for one row. Read amplification = 3× in pages, ~24× in bytes. But in practice, root and branch pages stay in the page cache (RAM), so actual disk reads drop to ~1×. That's why B-trees feel fast.

For LSMs, read amp is worse because you may check multiple SSTables before finding the key:

• Memtable: 0 disk reads
• L0 SSTables (3-10 files): potentially check each
• L1, L2, L3...: one disk read per level if Bloom filter doesn't rule it out

Without Bloom filters, an LSM read could touch 10+ files. With Bloom filters, most "is the key here" checks become RAM-only bit-array lookups, bringing read amp down to ~1.5–3×.

Why you care: read amplification drives p99 latency. Every extra page touched is another cache-miss opportunity, another network roundtrip (if cloud storage), another lock contention point.

3. Space amplification — "I have 100 GB of data; how much disk does it use?"

You have 100 GB of logical data. What actually consumes disk:

• Storage overhead per row (Postgres MVCC: ~24 bytes per row for xmin/xmax/etc.)
• Index space (a separate copy of the indexed column + a row pointer)
• Empty space in partially-filled pages (fillfactor: pages aren't 100% packed)
• Dead row versions waiting for VACUUM (Postgres MVCC)
• Old SSTables not yet compacted (LSM)
• Duplicate copies of the same key in different levels (LSM)

A Postgres DB might store 100 GB of logical data as 130 GB on disk. Space amplification ≈ 1.3×.

Cassandra with size-tiered compaction can hit 2–3× space amplification because the same data exists in multiple unmerged SSTables until compaction catches up.

Why you care:

• Disk costs money, especially on cloud (EBS, GCE PD aren't cheap at TB scale).
• More disk → fewer pages fit in page cache → worse cache hit rate → more disk reads → higher latency. The cascade matters.
• Backups take longer.

The triangle: you can't have all three

This is the key insight — the three amplifications trade off against each other. You can pick two corners but not all three at the same time:

How real engines sit in the triangle:

A concrete comparison: same data, two engines

Imagine storing the same 1 GB of data in Postgres and Cassandra:

Cassandra accepts higher space amp and read amp to get lower write amp. Postgres accepts higher write amp to get tight space and fast reads. Neither is "better" — they're optimised for different workloads.

When you understand this triangle, "which database?" almost always traces back to "what's your workload look like, and which corner do you want to live in?"

B-trees: how they actually work

The big idea

A B-tree is a balanced search tree where each node holds many keys (not just one like a binary tree). This makes the tree shallow — a 4-level tree can hold ~1.6 billion entries. Shallow trees mean few disk seeks per lookup.

Why "B"? Bayer and McCreight invented it in 1970. The "B" is debated; some say "balanced," some say "Bayer." Doesn't matter. What matters is the structure.

The page concept

A "page" is the unit of disk I/O. When the database reads or writes, it reads or writes whole pages — typically 4 KB, 8 KB (Postgres default), or 16 KB (InnoDB default). Even if you only need 100 bytes, you read the whole 8 KB page off disk.

Why pages? Because that's how operating systems and SSDs talk to disk. Read/write happens in fixed-size blocks at the hardware level. Trying to read 100 bytes off disk would still cause the OS to fetch a full page from the kernel buffer cache.

What's inside a page

A B-tree page is either an internal node or a leaf node:

Internal node (page):
+--------------------------------------------------------+
| header | key1 | ptr→child1 | key2 | ptr→child2 | ...   |
+--------------------------------------------------------+
"All keys < key1 are in child1; key1 ≤ k < key2 in child2; ..."

Leaf node (page):
+--------------------------------------------------------+
| header | (key1, value1) | (key2, value2) | ...         |
+--------------------------------------------------------+

The branching factor (how many keys fit per page) depends on key size. With 8 KB pages and ~50-byte (key+ptr) pairs, you fit ~160 entries per page. So the tree branches 160 ways at each level.

Tree depth math: at branching factor 160, a 1-level tree has 160 entries; 2 levels = 25,600; 3 levels = 4M; 4 levels = 650M; 5 levels = 100B. Most databases will never have a tree deeper than 4 or 5 levels.

Reading: walking the tree

To read key K:

1. Start at the root page. Find the child pointer for K (binary search the page; cheap).
2. Follow the pointer to the child page. Read it from disk.
3. Repeat until you reach a leaf.
4. Find K in the leaf. Return value.

Worst case: depth disk reads (5 disk reads for 100B keys). In practice, the upper levels (root + immediate children) stay in memory because they're touched on every read. So a typical read might be 1-2 actual disk reads, often 0 if the leaf is also cached.

Writing: in-place modification

To insert (K, V):

1. Walk to the leaf where K should live (same as reading).
2. Insert (K, V) into the leaf, keeping the leaf sorted.
3. If the leaf is full (no room for the new entry) → page split.

Page splits — the operation that gets interesting

flowchart TB
    A["Leaf page (full)
[10, 20, 30, 40, 50, 60, 70]"]
    A -->|"insert 35 — overflow"| B
    B["1. Pick median key (40)
2. Allocate new page
3. Log WAL split record"]
    B --> C["4. Update parent:
old child pointer →
(left, key=40, right)"]
    C --> D["Left leaf: 10, 20, 30, 35"]
    C --> E["Right leaf: 40, 50, 60, 70"]

When a page is full, the engine:

1. Allocates a new empty page.
2. Moves half the keys from the full page to the new page.
3. Updates the parent page to point to both pages, with a separator key.
4. If the parent is now full, it splits too — recursive.
5. If the root splits, tree height increases by one.

Cost of a split: rewrite of the full leaf, write of the new leaf, write of the parent. That's at least 3 page writes for one logical insert. This is part of write amplification.

Fillfactor: Postgres has a setting (fillfactor=70) that tells the engine to leave 30% free space in each page. This delays splits — inserts have somewhere to go without immediately splitting. Trades space for write performance.

The Write-Ahead Log (WAL) — the most important concept

Here's a problem: what if the database crashes mid-write? Say we're modifying a page on disk. The OS does a partial write. The page is now corrupt — half old data, half new data. Recovery has to be smart enough to handle this.

The solution: Write-Ahead Logging (also called journaling, redo logging). Before modifying any page, the database first writes a record describing the change to a separate file — the WAL.

To execute UPDATE accounts SET balance = 100 WHERE id = 42:

1. Find the page containing row 42 (walk the tree).
2. Hold the page in memory (page cache).
3. Generate a WAL record: "page X, offset Y, old=50, new=100".
4. Append the WAL record to the WAL file on disk.
5. fsync() the WAL file (force to disk).  ← THE DURABILITY POINT
6. Modify the in-memory page (set balance=100).
7. (Eventually, during checkpoint) write the dirty page to disk.

If the database crashes between step 5 and step 7, the modification is safe — recovery replays the WAL and re-applies the change. If the crash happens before step 5, the modification is lost but the database is consistent (the write never committed).

Why fsync() is so important — and so expensive

fsync() is the system call that forces the OS to flush its buffer cache to physical storage. Without fsync(), data may sit in the OS's write buffer for seconds before reaching disk. If the machine loses power in that window, you lose data.

Cost of fsync:

• Spinning HDD: 5–10 ms (a full rotation of the platter)
• Consumer SSD: 0.5–2 ms (depends on whether power-loss protection is implemented)
• Enterprise SSD with battery-backed cache: 50–200 µs
• Cloud block storage (EBS, GCE PD): 1–5 ms (network roundtrip)

Every committed transaction needs at least one fsync (to durably persist its WAL records). This is the practical bottleneck of transaction throughput on traditional disks.

Group commit: instead of one fsync per transaction, batch multiple transactions' WAL records into one fsync. If 100 transactions are committing in the same millisecond, one fsync covers them all — 100× throughput multiplier. Postgres does this automatically; the commit_delay setting tunes the batch window.

MVCC — making readers and writers stop blocking each other

Old databases used locking: if you're updating a row, no one else can read it until you commit. This is correct but slow under contention.

Modern databases use Multi-Version Concurrency Control (MVCC). Every row carries metadata:

• xmin: the transaction ID that created this version of the row.
• xmax: the transaction ID that deleted/replaced this version (or null if still live).

When a transaction starts, it gets a snapshot — basically a list of transaction IDs that have committed before it started. Reads filter rows: a row is visible if xmin is in the snapshot AND xmax is either null or not in the snapshot.

Updates don't modify the row in place. They write a new row version, set the old version's xmax to the current transaction ID, and the new version's xmin to the current transaction ID.

Result:

• Writers never block readers (readers see old versions).
• Readers never block writers (writers create new versions).
• Concurrent writers to the same row will conflict (locks or aborts kick in then).

The cost of MVCC: dead row versions and VACUUM

If every update creates a new row version, the old version stays around until no transaction can see it. Over time, you accumulate "dead tuples" — row versions that are invisible to any current transaction. They take space; they slow queries.

Postgres needs VACUUM to reclaim dead tuples. VACUUM is a background process that scans tables, identifies dead tuples, and marks their space as reusable.

Operational issues:

• VACUUM is I/O intensive. On a busy DB, it competes with queries.
• A long-running transaction (e.g., a 30-min analytics query) holds a snapshot for 30 min. VACUUM can't reclaim any row version newer than the oldest snapshot. Tables can bloat 10× during a single long transaction.
• autovacuum tries to run automatically. Tuning autovacuum is half of running Postgres at scale.

B-tree numbers worth memorising

• Branching factor: 100–500 depending on key size
• Tree depth: typically 3–4 levels for < 1B rows
• Cache hit rate at upper levels: 99%+
• Write amplification: 10–20× (WAL + page write + page split overhead)
• Read amplification: ~1× when leaf is cached, 1+depth misses when cold
• Space amplification: 1.1–1.3× (fillfactor + dead tuples before VACUUM)
• Sustained writes on commodity SSD: 10K–50K TPS with synchronous_commit on; 100K+ off

Used by: Postgres, MySQL InnoDB, Oracle, SQL Server, SQLite, MongoDB WiredTiger, etcd's BoltDB.

LSM-trees: the alternative

The big idea

What if we just... never modify in place? Every write appends. We organise the appended files later in the background. This trades read complexity (multiple files to check) for write simplicity (sequential, batched, never random).

This idea was published in 1996 (O'Neil et al., "The Log-Structured Merge-Tree"). It got popular when Google built Bigtable on it (2006). Today it powers Cassandra, RocksDB, LevelDB, HBase, ScyllaDB, InfluxDB, and most modern KV stores.

The mechanics, step by step

Step 1 — Write to memory. A write goes to an in-memory sorted data structure called the memtable. Typically a skip list or red-black tree. Skip lists are popular because they're simpler to make concurrent.

Step 2 — Append to WAL. Simultaneously, the write is appended to a Write-Ahead Log on disk (same idea as B-tree WAL). This makes the write durable even before it lands in an on-disk structure.

Step 3 — When memtable fills, flush. When the memtable hits a size threshold (e.g., 64 MB), it's flushed to disk as an immutable, sorted file: an SSTable (Sorted String Table). The memtable becomes a new empty one; writes continue.

Step 4 — Background compaction. Over time, you accumulate many SSTables. The DB has a background process — compaction — that merges multiple SSTables into a larger one, discarding overwritten keys and tombstones.

Reading from an LSM

To find key K:

1. Check the memtable. Found? Return.
2. Check each SSTable, newest to oldest. The newest version of K wins.
3. If we reach the end without finding K, return "not found."

Naively, this could mean checking N SSTables per read. If N=20, that's 20 disk seeks. Way too slow. Two optimisations make LSM reads fast:

Bloom filters

A Bloom filter is a small probabilistic data structure that answers "is X in this set?" with two possible answers:

• "Definitely not in" (zero false negatives)
• "Maybe in" (small false-positive rate, e.g., 1%)

Each SSTable has a Bloom filter for its keys. To read key K, you check each SSTable's Bloom filter first. If it says "definitely not in," you skip that SSTable entirely — no disk read. You only actually read SSTables whose Bloom filters say "maybe in."

With a 1% false positive rate, reading a missing key requires ~1.2 actual SSTable reads instead of N. Bloom filters typically use ~10 bits per key — so 1 billion keys = 1.25 GB of Bloom filter memory. Keep it in RAM.

Level structure

flowchart TB
    W["Write"] --> M["Memtable (RAM, sorted, ~64MB)"]
    M -->|flush when full| L0["L0: small SSTables
overlapping key ranges"]
    L0 -->|compact when L0 grows| L1["L1: ~10MB SSTables
non-overlapping"]
    L1 -->|leveled compaction| L2["L2: ~100MB SSTables
non-overlapping"]
    L2 --> L3["L3: ~1GB SSTables"]
    L3 --> LN["Lₙ: each ~10× previous
(typical depth 5–7)"]

Instead of one big pile of SSTables, organize them in levels:

L0 — newly flushed SSTables. May overlap in key range.
L1 — sorted, non-overlapping SSTables. Total size ~10 MB.
L2 — sorted, non-overlapping. Total ~100 MB.
L3 — sorted, non-overlapping. Total ~1 GB.
L4, L5, L6 — each 10× larger.

Reads at L1+ can use binary search: each level has a sorted index. Reads at L0 must check each L0 file (because they overlap). L0 is kept small (typically max 4 files).

Compaction strategies — the most important LSM concept

Compaction takes multiple SSTables and merges them. Different strategies trade write amplification, read amplification, and space amplification differently.

Why compaction is the operational beast of LSM

Compaction is constantly running in the background. It reads SSTables, merges them, writes new ones, deletes old ones. This consumes CPU and I/O.

If compaction can't keep up with writes:

• L0 SSTables accumulate.
• Read amplification spikes (many SSTables to check).
• RocksDB starts throttling writes (slowdown threshold).
• Eventually it stops writes entirely (stall threshold).

This manifests as periodic write-latency spikes during heavy ingest. Tuning compaction (rate limiting, parallelism, thresholds) is a senior skill.

Tombstones — how LSMs handle deletes

You can't actually delete a row from an LSM cheaply — the row might exist in 5 different SSTables. So a delete writes a tombstone: a marker saying "this key is deleted."

The tombstone wins over any older value of the key. During compaction, when a tombstone meets the row it overrides, both can be discarded.

Tombstone problems:

• Tombstones aren't removed until they're and the original key are in the same SSTable during a compaction. Until then, both exist.
• Range scans must read past tombstones. A range with 1,000 deleted entries causes 1,000 wasted reads.
• Cassandra has a gc_grace_seconds (default 10 days!) — tombstones must live this long before compaction. Otherwise zombie data resurrects: if a replica missed the delete and a tombstone gets cleaned up before that replica catches up, the deleted row reappears when reconciled.

LSM numbers

• Write amplification: 10–30× for leveled, 50–100× under bad workloads
• Read amplification: 1.5–3× with Bloom filters, 5–20× without
• Space amplification: 1.1× leveled, 2–3× size-tiered
• Sustained writes: 100K+ ops/sec per node easily; 500K+ for write-only workloads
• Compaction CPU overhead: 20–40% of total CPU under load

Used by: Cassandra, RocksDB, LevelDB, ScyllaDB, HBase, Bigtable, DynamoDB (internally), CockroachDB (via Pebble), InfluxDB, Kafka log compaction.

How to choose — and what real systems pick

Interview drills

Red flags candidates show on this topic

• "LSM is always faster than B-tree" — wrong; depends on workload.
• "WAL is for replication" — wrong; WAL is for durability. Replication often uses WAL as the source.
• "MVCC means no locks at all" — wrong; there are still latches, just no row-level read-blocks-write.
• Cannot explain why fsync is expensive.
• Doesn't know what page splits cost.
• Confuses tombstones with deleted-row markers in B-trees (different concept).