Start practising

SYSTEM DESIGN · CONCEPTS · DATABASES · EPISODE 23

Storage Engines: B-Trees vs LSM Trees

What a database actually does with a row: the write-ahead log, B-tree pages that update in place, LSM trees that append and compact, read vs write amplification, and which engine sits under PostgreSQL, MySQL, Cassandra and RocksDB.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
1 / 12

Press play to hear the narration, or step through at your own pace. Every picture here is the same one used in the YouTube video.

Notes

Write-ahead log

Before either tree, one shared trick. Every write is first appended to a write-ahead log and flushed to disk. Only then does the engine touch its real data structure. If the process dies halfway, it replays the log on restart. Appending to a file is the fastest thing a disk can do, so the WAL makes writes both durable and cheap.

Step 0: the WAL
  • append the change to a log file
  • fsync it: now it is durable
  • then update the real structure
  • crash in between? replay the log
  • appending is the fastest thing
  • a disk can do

B-tree

Option one: the B-tree, the engine under PostgreSQL, MySQL's InnoDB and most relational databases. Data lives in fixed-size pages, usually eight kilobytes. The root page points to branch pages, which point to leaf pages holding the rows. Each page holds hundreds of keys, so a billion rows is only four levels deep. Finding a row is four page reads, and three of those are almost always cached in RAM.

B-tree: pages
disk = fixed pages (8 KB)
root → branch → leaf
each page: sorted keys +
  pointers to child pages

fan-out ~500 per page
1 billion rows = 4 levels
lookup = 4 page reads

B-tree writes

Writing is where the B-tree pays. To change a row you find its leaf page and rewrite that whole page, eight kilobytes for a hundred-byte change. If the page is full, it splits in two and the parent is updated. And because rows land wherever their key says, writes are scattered randomly across the disk. Reads: great. Heavy random writes: the weak spot.

B-tree: writing
  • find the leaf, change it in place
  • rewrite the whole 8 KB page
  • even for a 100-byte row
  • page full? split into two,
  • update the parent
  • random writes, all over the disk

LSM tree

Option two: the log-structured merge tree. A write goes to the WAL and into a memtable, a sorted structure in RAM. That's it; the write is done in a microsecond. When the memtable fills, say sixty-four megabytes, the engine writes it out as one sorted file, an SSTable, in a single sequential pass. That file is never modified again. Every disk write is sequential, which is why Cassandra can take a hundred thousand writes a second on one node.

LSM tree: writing
write → WAL + memtable (RAM,
  sorted, e.g. a skip list)

memtable full (64 MB)?
  write it to disk as one
  sorted file: an SSTable
  never modified again

writes are sequential, always

LSM reads

Now the LSM pays. A key could be in the memtable or in any SSTable, so a read checks the memtable and then every file from newest to oldest; the newest copy is the current value. Twenty files could mean twenty disk reads. Two fixes. Each SSTable carries a Bloom filter, a tiny bitmap that says 'this key is definitely not in here', so most files are skipped without a read. And compaction keeps the file count down.

LSM tree: reading
  • check the memtable
  • then each SSTable, newest first
  • (newest wins: it is the latest
  • version of that key)
  • many files = many reads
  • fixes: Bloom filter per file
  • ("key definitely not here")
  • + compaction (next)

Compaction

Compaction is a background job that merges several SSTables into one. Since every file is sorted, merging is a single sequential pass. Old versions of a key and deleted keys, marked with tombstones, are dropped on the way. Files are organised into levels, each ten times bigger than the last, so a read touches at most one file per level. The cost: compaction burns disk bandwidth and CPU, and can stall writes when it falls behind.

Compaction
  • background job: merge several
  • SSTables into one bigger one
  • (both sorted: a merge is a
  • single sequential pass)
  • drops overwritten versions
  • and deleted keys (tombstones)
  • levels: L0 10 MB → L1 100 MB
  • → L2 1 GB …

The trade

Engineers compare engines by amplification. Write amplification: how many bytes hit the disk per byte you wrote. The B-tree rewrites a whole page per row. The LSM rewrites each row once per compaction level. Read amplification: how many disk reads per lookup. The B-tree needs about one. The LSM needs one per level, minus whatever Bloom filters skip. Neither wins; they trade.

Amplification
write amplification:
  bytes written to disk
  per byte the app wrote
  B-tree: rewrite 8 KB per row
  LSM: rewrite on each compaction

read amplification:
  disk reads per lookup
  B-tree: ~1 (rest cached)
  LSM: 1 per level, minus Bloom

In the wild

Who uses what. B-trees: PostgreSQL, MySQL, SQLite, Oracle, SQL Server. LSM trees: Cassandra, HBase, LevelDB, and RocksDB, which sits under CockroachDB, TiDB and Kafka Streams. The pattern: relational databases that expect mixed reads and writes with transactions chose B-trees; write-heavy distributed stores chose LSM.

Who uses what
  • B-tree:
  • PostgreSQL, MySQL (InnoDB),
  • SQLite, Oracle, SQL Server
  • LSM tree:
  • Cassandra, HBase, RocksDB
  • (→ CockroachDB, TiDB, Kafka
  • Streams), LevelDB, ScyllaDB
  • MongoDB WiredTiger: B-tree
  • with LSM option

Decision

How to choose. Read-heavy with point lookups, range scans and transactions: B-tree. A firehose of writes, logs, events, metrics, time series: LSM. In practice you rarely pick the engine directly; you pick it by picking the database. Choose PostgreSQL and you get a B-tree. Choose Cassandra and you get an LSM tree. Knowing which one you got explains how it behaves under load.

How to choose
  • read-heavy, point lookups,
  • range scans, transactions
  • → B-tree
  • write-heavy: logs, events,
  • metrics, time series, IoT
  • → LSM tree
  • most apps: B-tree is fine;
  • you pick LSM by picking Cassandra

Say it like this

The interview answer. Both engines log every write first. The B-tree then updates pages in place, random I/O, but a lookup is one page read. The LSM appends to a memtable and flushes sorted files sequentially, so writes are fast, but a read may touch several files, which Bloom filters and compaction keep in check. Say 'write amplification' and 'read amplification' and the interviewer knows you've seen the inside.

In the interview
  • "Why is Cassandra fast at writes
  • but PostgreSQL faster at reads?"
  • 1. WAL makes any write durable
  • 2. B-tree: in-place page writes,
  • random I/O, one read per lookup
  • 3. LSM: sequential flushes,
  • many files per read,
  • Bloom filters + compaction

Interview questions

What is a write-ahead log and why do both engine types use it?

An append-only file that every change is written and fsynced to before the main data structure is updated. Appending is sequential and fast, and if the process crashes mid-update the log is replayed on restart, so writes are durable without having to flush the whole tree.

How does a B-tree keep lookups fast for a billion rows?

Data is stored in fixed-size pages (typically 8 KB) with hundreds of keys per page, giving a fan-out of a few hundred. A billion rows fit in about four levels, so a lookup is four page reads, and the upper levels are almost always cached in memory.

Why are heavy random writes the weak spot of a B-tree?

Changing one row means rewriting its entire page (write amplification), pages that fill up must split and update their parent, and rows land wherever their key dictates, so the disk sees scattered random writes rather than sequential ones.

Describe the write path of an LSM tree.

The write goes to the WAL and into an in-memory sorted memtable, then returns. When the memtable is full it is written to disk sequentially as an immutable sorted file (SSTable). All disk writes are sequential, which is why LSM engines sustain very high write rates.

Why can reads be slow in an LSM tree, and what fixes that?

A key may live in the memtable or in any SSTable, so a read may check many files newest-first. Bloom filters let the engine skip files that definitely do not contain the key, and compaction merges files into levels so a read touches at most one file per level.

What does compaction do and what does it cost?

A background job that merges several sorted SSTables into one bigger one in a single sequential pass, dropping overwritten versions and tombstoned deletes. It costs disk bandwidth and CPU, and if it falls behind it can stall writes.

Define write amplification and read amplification.

Write amplification is the number of bytes written to disk per byte the application wrote (high for B-tree page rewrites and for LSM re-compaction across levels). Read amplification is the number of disk reads per lookup (about one for a B-tree, up to one per level for an LSM tree before Bloom filters).

Which engine would you choose for an event-logging service, and which for an order system?

Event logging is a write-heavy firehose with mostly recent-data reads, so an LSM-based store (Cassandra, RocksDB-backed databases) fits. An order system needs point lookups, range scans and transactions across mixed reads and writes, so a B-tree relational database (PostgreSQL, MySQL) fits.