The Storage Engine: Where the Data Actually Lives

A database’s storage engine is the layer that manages how rows/keys are laid out on disk. It is the reason two “PostgreSQL-compatible” or “Cassandra-like” systems can have wildly different performance: the engine is the performance. The two dominant designs are B-trees and LSM trees, and choosing between them is the first big data-engineering decision you’ll ever make.

B-Trees: The Read-Optimized Workhorse

A B-tree keeps keys in sorted order in a balanced, wide tree. Every key lives at a known position; finding it costs O(log_B n) page reads — a few disk reads even for billions of keys. Updates are in-place: the database finds the page and overwrites it.

• Strengths — excellent reads, strong read amplification story (one point read ≈ one seek), stable, battle-tested. Used by PostgreSQL, MySQL/InnoDB, SQLite.
• Weakness — writes touch random pages. Every small write is a random disk write somewhere in the tree; on spinning disks or busy systems that’s the bottleneck. Random in-place updates also mean the tree needs WAL (write-ahead log) so a crash mid-update can be replayed — and the log is itself a write.

LSM Trees: The Write-Optimized Design

LSM (Log-Structured Merge) trees invert the strategy: never update in place; instead buffer writes in memory and flush sorted files to disk, merging them later.

The write path has three stages:

1. Write-Ahead Log (WAL) — every write is first appended to an append-only log on disk. This is the durability guarantee: crash recovery replays the log.
2. Memtable — the write is also inserted into an in-memory sorted structure (often a skip list or balanced tree). Reads check the memtable first.
3. SSTables — when the memtable fills, it’s flushed to disk as a sorted, immutable SSTable (Sorted String Table). New flushes create new SSTables.

Because writes are (a) appended to a sequential log and (b) inserted in memory, there are no random disk writes on the write path — that’s the LSM superpower, and it’s why RocksDB, LevelDB, Cassandra, and HBase eat write-heavy workloads alive.

Compaction: The Ongoing Merge

Immutable SSTables pile up, so the engine periodically compacts them — merging overlapping SSTables into new sorted files and dropping obsolete/deleted keys. This is a background process and the source of LSM’s main pain:

• Write amplification — the same byte may be rewritten several times across compactions (memtable → SSTable → merged SSTable).
• Read amplification — a point read may have to check the memtable and several SSTables before finding the key.

Engines control this with compaction strategies: level-based (e.g., RocksDB’s leveled: each level is one sorted run, exponentially larger) vs size-tiered (Cassandra: merge same-size tables). Tuning is the art of trading write cost against read cost.

Bloom Filters: The Read-Amp Escape Hatch

To stop a point read from scanning every SSTable, LSM engines keep a Bloom filter per SSTable: a probabilistic structure that can say “definitely not here” with certainty. A read asks each SSTable’s filter first; only the tables whose filter might contain the key get probed. This is why LSM reads are fast in practice despite many files.

B-Tree vs LSM: The Trade-off

The engineering rule of thumb: OLTP with a moderate write rate and read-heavy workloads → B-tree. High-volume event/telemetry ingestion with many writes → LSM. And if you care, the “merge” itself is the same merge you know from Merge Sort — this whole system is algorithms wearing a database costume.

Practice Trajectory

1. Trace one INSERT through a B-tree engine: WAL append → in-place page update; then through LSM: WAL append → memtable insert.
2. Explain why an append-only log is fast on disks and why random in-place writes are slow.
3. Show how a Bloom filter turns “must check 6 SSTables” into “check 1.”
4. Given a workload of 90% writes / 10% reads (telemetry), justify an LSM engine; for 95% reads, justify a B-tree.
5. Describe the compaction cascade in RocksDB leveled mode and where write amplification is spent.

When It’s the Right Tool