Lesson 5.2• 9 min read

Storage engines: B-trees versus LSM-trees

In-place page updates, append-only logs, MemTables, SSTables, Bloom filters, and compaction.

What you will learn

Explain how a B-tree updates pages in place.
Follow a write and a read through an LSM-tree: write-ahead log, memtable, SSTables, Bloom filters and compaction.
Measure write amplification, and say which engine suits which workload.

The fundamental trade-off: Reads vs. Writes

At the heart of every database is an on-disk storage engine. The two dominant designs make opposite trade-offs:

B-trees: Keep data sorted in a tree of fixed-size pages and update pages where they are. Good for point reads and range scans.
Log-structured merge trees (LSM-trees): Defer and batch changes, writing them to disk in large sequential runs. Designed for a high rate of inserts.

1. B-tree architecture (update in place)

Used by most relational databases (PostgreSQL, MySQL's InnoDB):

Structure: A balanced tree of fixed-size pages (PostgreSQL stores every table and index as pages, usually 8 kB).
Point reads: Walk from the root to the leaf that holds the key: about $\log(N)$ pages, and the upper levels are usually already in memory.
Writes: Find the leaf page that holds the key, change it, and write the page back, after first recording the change in the write-ahead log.
Write amplification: Changing a 50-byte record can mean writing a whole 8 kB page plus the WAL record: $\frac{8192}{50} \approx 164\times$ more bytes than the change itself, in the worst case of a page written for a single change.
Under heavy inserts: Every insert lands on whichever page holds its key, so maintaining an index under a high insert rate costs many random disk I/Os. The LSM-tree paper reports that keeping one such index in real time with a B-tree effectively doubles the I/O cost of each transaction.

2. LSM-tree architecture (append and compact)

Used by Cassandra, RocksDB, LevelDB and Bigtable-style stores:

Write-ahead log (WAL): A write is appended sequentially to a log for crash durability.
Memtable (RAM): The write goes into an in-memory sorted structure (RocksDB's default is a skip list), and is then acknowledged.
SSTable flush: When the memtable is full (RocksDB's default size is 64 MB), it is written out as an immutable, sorted file (an SSTable). Flushes are large sequential writes.
Reads: Check the memtable first, then SSTables from newest to oldest. A key may be in any of them.
Bloom filters: Each SSTable has an in-memory filter that answers either "the key may be here" or "the key is definitely not here". A "definitely not" lets the read skip that file entirely; a "maybe" still requires a look.
Compaction: A background process merges SSTables into fewer sorted runs, so reads have fewer places to check and old versions stop taking space. The compaction strategy trades write amplification against read and space amplification.

\text{Write amplification} = \frac{\text{Total bytes written to storage}}{\text{Bytes written by the application}}

The trade-off: LSM-trees make writes cheap by deferring and batching them, but a read may have to look in several places (Bloom filters limit the damage), and compaction rewrites data repeatedly in the background, which is write amplification of its own. B-trees do more work per write but keep each key in exactly one place.

B-trees versus LSM-trees

Simulation workload:

LSM-tree write & flush pipeline:

1. Write-Ahead Log

Sequential disk append for instant crash durability.

2. MemTable (RAM)

Sorted red-black / SkipList buffer in memory.

3. Bloom Filter

Fast negative check in RAM (avoids disk reads).

4. SSTables (Disk)

Immutable sorted runs (L0..L2).

Write costCheap: batched and sequentialAppend to the WAL, insert into the memtable, flush sorted SSTables

Point readsBloom filters skip most SSTablesUsually one SSTable per lookup

Write amplificationData is rewritten by each compactionBytes written to disk per byte the application writes

Primary design targetWrite ingestion & time-seriesWrite-heavy data: time series, logs, event streams

Key takeaways

B-trees keep each key in exactly one place, so reads and range scans are cheap, but every write rewrites a page, and heavy inserts cost random I/O.
LSM-trees append to a log and a memtable, then flush sorted, immutable SSTables in large sequential writes, which makes writes cheap.
An LSM read may check several SSTables; Bloom filters skip the ones that definitely lack the key, and compaction merges files at the cost of rewriting data.
Write amplification is total bytes written to storage divided by bytes the application wrote.

Sources

Adapted from The System Design Primer by Donne Martin, licensed under CC BY 4.0. Changes were made.