Storage · 1 of 3

Storage Engines

Every database is a bet about where to pay for writes. B-trees pay up front by updating pages in place; LSM-trees pay later by merging immutable files in the background. Here's how each works, and how each fails.

≈ 25 min

The whole idea

B-tree: update in placeLSM-tree: append, merge later
Press ← → to step, or Space to play and pause, whenever a diagram has focus.

The simplest database

A storage engine is the part of a database that decides how bytes sit on disk. Its job sounds simple: store a value under a key, and give it back later. Doing both quickly, durably and at scale is where every interesting design comes from.

Start with the smallest thing that works. A set appends key,value to the end of a file; a get reads the file and returns the last value it saw for that key. Appending is the cheapest write any disk can do, and many real databases keep exactly this kind of append-only log at their core.

Fast writes, slow reads

An append-only file is a perfectly good database until you need to read from it.

The log is fast to write and hopeless to read: every get scans the whole file. The fix is an index, an extra structure derived from the data that tells you where to look. An in-memory hash map from each key to its byte offset is enough to make reads one seek; Riak’s Bitcask engine works roughly like this. But it has two hard limits. Every key must fit in RAM, and a hash map can’t answer range questions like “all keys between user:100 and user:200”.

So real engines keep data sorted by key, which makes ranges cheap and lets an index be sparse. There are two families of answer to “how do you keep data sorted while writes arrive in random order?”, and they run almost every database you use:

  • Update in place. Keep a sorted tree of fixed-size pages on disk and overwrite the right page on every write. That’s the B-tree: Postgres, MySQL’s InnoDB, SQLite, SQL Server, Oracle.
  • Append, then merge. Buffer writes in memory, write them out as sorted immutable files, and merge those files in the background. That’s the LSM-tree: RocksDB, Cassandra, ScyllaDB, HBase, and the engines under CockroachDB and TiKV.

The write-ahead log

Both families share one rule: every change is first written down in an append-only log, and that log record must reach disk before the changed data does. A transaction counts as committed once its log records are on stable storage. That’s the write-ahead log (WAL). If the machine dies mid-change, the log is the record of truth, and recovery replays it.

Durability, then speed

The client hears “committed” only after the log record is on stable storage. Everything else can be lazy.

The WAL turns many scattered random writes into one sequential append per transaction, and lets the database keep its real data structures in memory, flushing them whenever it’s convenient. Two details make it work in practice:

  • fsync is the commit point. A write() only reaches the operating system’s page cache. Until fsync returns, a power cut can still lose it. Because fsync waits for the device, it’s the slowest step in a commit, so databases use group commit: many concurrent transactions share one fsync.
  • Pages can tear. A database page (8 KB in Postgres, 16 KB in InnoDB) is bigger than the unit a disk writes atomically, so a crash can leave half an old page and half a new one. Postgres guards against this by logging a full image of each page the first time it changes after a checkpoint (full_page_writes); InnoDB writes pages to a doublewrite buffer first.

LSM-trees

The log-structured merge-tree was described by Patrick O’Neil and colleagues in 1996, and Google’s Bigtable (2006) gave its parts the names everyone still uses. It never modifies a file once written. Writes go to two places:

  1. The WAL, in arrival order, for durability.
  2. The memtable, an in-memory sorted structure (RocksDB’s default is a skip list), which is where writes are actually read from until they reach disk.

When the memtable reaches its size limit (64 MB by default in RocksDB), it becomes immutable and is flushed to disk as an SSTable, a sorted string table: key-value pairs in key order, split into small blocks, with an index of where each block starts. Because the file is sorted, an in-memory index of one key per block is enough to find any key with a single block read. After the flush, the log records that covered that memtable are no longer needed; RocksDB deletes a WAL file once everything in it has been flushed.

Inside an LSM-tree

Memory · memtable empty
Disk · write-ahead log (append order)empty
L0flushed files, may overlap
no files
L1compacted, no overlap
no files
Writes land in memory, files are never edited, and reads go newest to oldest. Step through to see a flush, an overwrite, a delete and a compaction.

Three consequences fall out of “files are immutable”:

  • Updates and deletes are just more writes. Overwriting cat leaves the old value in an older file; the newer file shadows it. A delete writes a tombstone, a marker that says “this key is gone”, which also shadows older values until compaction removes both.
  • Reads check newest to oldest: memtable, then each file in turn, stopping at the first hit. A read for a key that lives in an old file, or doesn’t exist at all, may have to look in many places. That’s read amplification.
  • Writes are always sequential. Flushes and merges write big sorted files from start to finish, which is what lets an LSM-tree absorb very high write rates.

Compaction

Left alone, files pile up, reads get slower and dead values waste disk. Compaction is the background process that merge-sorts several SSTables into new ones, keeping only the newest version of each key and dropping tombstones once nothing older could still hold the key. Merging sorted files is cheap and sequential, like the merge step of merge sort. The interesting question is which files to merge, and when. Two strategies dominate.

Leveled compaction (RocksDB’s default; LevelDB’s only mode) arranges files in levels. L0 holds fresh flushes, which may overlap. Every level below is a single sorted run of non-overlapping files, each level about 10× larger than the one above. When a level grows past its target, one of its files is merged into the overlapping files of the next level down. A read checks at most one file per level below L0, and with dynamic level sizing (RocksDB’s default since version 8.4) about 90% of the data sits in the last level, so space overhead is small. The price is that each byte gets rewritten once per level it passes through.

Size-tiered compaction (Cassandra’s default; RocksDB calls its variant universal) waits until there are several files of similar size and merges them into one bigger file. Each byte is rewritten far fewer times, so writes are cheaper. But a key can now live in many overlapping files, so reads check more of them, and a big merge needs room for the inputs and the output at once, so RocksDB’s docs warn it can temporarily double the space used.Cassandra 5.0 added a Unified Compaction Strategy, now the one its docs recommend, that can behave like either, tuned per table, rather than forcing an up-front choice.

Leveled Size-tiered / universal
Write amplification high (often over 10×) low
Read amplification low: about one file per level higher: many overlapping files
Space amplification low (≈ 10–14% extra) high, up to 2× during big merges
Good for read-heavy, space-constrained write-heavy, append-mostly, time-series

Bloom filters

A read for a key that’s absent, or old, would touch every file on its way down. LSM engines avoid most of that with a Bloom filter per SSTable: a compact, in-memory summary that answers “is this key in the file?” with either definitely not or maybe.

How a Bloom filter answers

keys added: none00010203040506070809010011012013014015
Bits are only ever set, never cleared, so a 0 is proof of absence and all 1s is only a hint.

It’s a bit array of m bits and k hash functions. Adding a key sets the k bits it hashes to. Checking a key looks at the same k bits: if any is 0, the key was never added. If all are 1, it probably was, but other keys may have set those bits: a false positive. There are no false negatives. With n keys, the false-positive rate is about (1 − e−kn/m)k, minimised at k ≈ 0.69 · m/n.

10 bitsper key: RocksDB’s recommended Bloom filter setting
≈ 1%false-positive rate at 10 bits per key
−30%filter memory with RocksDB’s Ribbon filter, for 3–4× the CPU to build it

Skipping files

The filters live in memory; the files live on disk. Every “definitely not” is a disk read that never happens.

Filters only help point lookups. A range scan has no single key to hash, so it still has to visit every file whose key range overlaps; RocksDB’s prefix Bloom filters exist to win some of that back when queries share a known key prefix.

B-trees

The B-tree is older than most programmers: Rudolf Bayer and Edward McCreight described it in 1970, and by the end of that decade it was already the standard database index. It’s still the default almost everywhere.

A B-tree breaks the data into fixed-size pages and arranges them as a tree. Interior pages hold separator keys and pointers to children; leaf pages hold the entries themselves (most databases use the B+tree variant, where only leaves hold data and leaves link to their neighbours for fast range scans). A lookup starts at the root and follows one pointer per level down to the right leaf.

What keeps the tree shallow is fanout. A page holds hundreds of keys, so each level multiplies the reach by hundreds. Ben Dicken’s estimate for a 16 KB page (InnoDB’s default) holding 8-byte keys, values and child pointers is about 682 entries per page, which puts roughly 317 million rows within three levels. Add a fourth and you’re into the hundreds of billions. The top levels are tiny and stay cached, so a lookup costs about one disk read.

Lookup and split

root pageleaf pages · sorted · linked left to right20405101520253035404550
A tree with tiny four-key pages. Real pages hold hundreds of keys, but they split in exactly the same way.

Writes are where the B-tree earns its complexity. A new key goes into the leaf that covers it. If that page is full, it splits into two half-full pages, and a new separator is inserted into the parent, which may split in turn. If the root splits, the tree gains a level at the top, so every leaf is always at the same depth.

A split rewrites several pages as one logical change, and a crash between them would corrupt the tree. That’s why B-trees lean on the WAL so heavily: the split is logged first, so recovery can finish or undo it. It’s also why concurrent B-trees need careful latching on pages: two writers splitting neighbouring pages must not see each other’s half-finished work.Some engines avoid in-place overwrites entirely. LMDB uses a copy-on-write B-tree: a write copies the changed pages and the path above them, then atomically switches to a new root, which also gives readers consistent snapshots for free.

Write amplification

Write amplification is the ratio of bytes the engine writes to disk to bytes you asked it to write. It’s the number that decides how much disk bandwidth your writes really cost, and how fast you wear out an SSD.

Both families amplify, for different reasons:

  • A B-tree rewrites a whole page to change a few bytes in it, and writes the change to the WAL as well, plus a full page image the first time a page changes after each checkpoint. Small random updates spread across many pages are its worst case.
  • An LSM-tree writes each byte to the WAL, then to L0, then again every time compaction pushes it down a level.

Where 33× comes from

The worked example from RocksDB’s tuning guide: a 500 GB database, L1 = 512 MB, each level 10× larger.

For leveled compaction the arithmetic is simple: roughly one rewrite per level, times the size ratio between levels. RocksDB’s tuning guide works through exactly this example and lands at about 33×. Size-tiered compaction cuts this a lot, at the cost of read and space amplification. That three-way tension between write, read and space amplification is the core of LSM tuning: you can improve any two at the expense of the third.

B-trees vs LSM-trees

There’s no winner, only workloads.

B-tree LSM-tree
Write path find the page, overwrite it in place append to memtable, flush and merge later
Write throughput good; random page writes very high; sequential writes
Point reads one root-to-leaf path, predictable memtable, every L0 file, then at most one file per lower level; Bloom filters help
Range scans excellent: leaves are sorted and linked good, but must merge several sorted files
Space pages are often partly empty after splits compact once compacted; tombstones linger until then
Latency steady background compaction can cause spikes and stalls
Each key lives… in exactly one place, handy for locking in several files until compaction catches up

Rules of thumb that hold up:

  • Write-heavy, append-mostly or huge data sets (event logs, time series, message stores, metrics) favour LSM-trees.
  • Read-heavy OLTP with in-place updates and range scans favours B-trees, which also give the most predictable latency.
  • Measure in steady state. An LSM benchmark run before compaction has caught up flatters it badly.

In the real world

RocksDB is the reference LSM engine. Facebook forked it from Google’s LevelDB, and today it’s embedded almost everywhere: Kafka Streams state stores, Apache Flink’s large-state backend, TiKV, and many more. Its defaults tell you what it’s tuned for: leveled compaction, 64 MB memtables, 4 KB blocks, and the advice to use ~10-bit Bloom filters per key.

½storage used by Facebook’s main user database after moving from compressed InnoDB to MyRocks (2017)
60 → 20 msP99 read latency on one Instagram Cassandra cluster after swapping in RocksDB (2018)
up to 3×read speed-ups from Postgres 18’s new asynchronous I/O (2025)
  • Facebook’s user database (UDB), which stores the social graph, was space-bound on flash even with InnoDB compression. Its team built MyRocks, MySQL on top of RocksDB, and finished migrating UDB in August 2017. It cut storage usage in half. Part of the win is structural: B-tree pages are left partly empty by splits, while LSM files are written densely and compressed block by block.
  • Instagram found that much of its Cassandra tail latency came from JVM garbage-collection pauses in the storage engine itself. Its 2018 Rocksandra project replaced that engine with RocksDB; on one production cluster P99 reads fell from 60 ms to 20 ms and GC stalls from 2.5% to 0.3% of the time.
  • CockroachDB ran on RocksDB from its first release until Pebble, a RocksDB-inspired LSM engine written in Go, became its default storage engine in v20.2 (November 2020).
  • Postgres stays firmly in the B-tree camp, with 8 KB pages, a WAL with full-page images, and a separate heap for table rows (more on that in the next lesson). Postgres 18 (September 2025) added an asynchronous I/O subsystem with up to 3× faster reads from storage in benchmarks.
  • Filters keep improving. RocksDB added the Ribbon filter (experimental in 6.15 in 2020, production-ready in 6.22), which matches a Bloom filter’s 1% false-positive rate in about 7 bits per key instead of 10, trading construction CPU for roughly 30% less memory.

Pitfalls

  • Trusting that write() means durable. Only a successful fsync (or O_DSYNC) does, and even then every layer below, down to the drive’s own write cache, must honour the flush. And a failed fsync must be treated as fatal, not retried.
  • Compaction debt. If writes outpace compaction, L0 fills up and reads slow down; RocksDB then stalls writes on purpose until compaction catches up. Watch pending-compaction bytes, not just disk usage.
  • Tombstone trouble. In an LSM, deleting a million rows adds a million records. Scans over deleted ranges wade through tombstones, and in a replicated store like Cassandra, if a replica that missed the delete isn’t repaired within gc_grace_seconds (10 days by default), the tombstone can be purged and that replica brings the row back to life.
  • Random keys in a B-tree. UUIDv4 primary keys scatter inserts across every leaf, causing more page splits, more cache misses and half-empty pages. Time-ordered keys like UUIDv7 append at the right edge instead.
  • Expecting Bloom filters to speed up range scans. They only answer “is this exact key here?”
  • Benchmarking a fresh LSM. Its first hour, before compaction reaches steady state, is not the workload you will run in production.

Recall

Go deeper

Keep going

The atomic notes for this lesson live in the knowledge graph:

Next on the map: Indexes & Search (secondary, clustered, inverted and vector indexes) and Analytics & Columnar Storage (laying data out by column instead of by row).

Done with this lesson?

Mark it learned and the concepts it teaches will light up in your galaxy.

Next in StorageIndexes & Search