Storage Engines¶

What a storage engine is¶

A database has two halves. The upper half parses SQL, plans queries, and manages transactions and sessions (see SQL Execution Flow). The lower half — the storage engine — answers a much narrower question: given keys and values (or rows and pages), how are they laid out in memory and on disk so they can be written, found, and recovered after a crash?

Its interface is small:

type Engine interface {
    Put(key, value []byte) error
    Delete(key []byte) error
    Get(key []byte) ([]byte, error)
    NewIterator(start []byte) Iterator // ordered iteration
    Write(b *Batch) error              // several changes atomically
}

Behind that interface, every engine is built from the same handful of components:

Engines are often pluggable: MySQL can run InnoDB or MyRocks (RocksDB); MongoDB runs WiredTiger; CockroachDB runs Pebble; TiDB's storage layer TiKV runs RocksDB.

The two dominant families¶

B+Tree: update in place¶

Data lives in fixed-size pages (typically 4–16 KB) organized as a balanced tree. A write finds the leaf page that owns the key and modifies it — in the in-memory buffer pool first, written back to disk later. Reads descend the tree: with a fan-out of a few hundred, three or four page reads reach any key among billions, and the top levels are almost always cached.

Used by: PostgreSQL, MySQL InnoDB, SQL Server, Oracle, SQLite, WiredTiger (default), LMDB, BoltDB.

LSM tree: log-structured merge¶

Writes never modify data on disk. They go into an in-memory sorted memtable; when it fills, it is written out as an immutable sorted file (SSTable). Background compaction merges SSTables to drop overwritten and deleted entries and keep the number of files a read must consult small. Reads check the memtable, then SSTables from newest to oldest, using Bloom filters to skip files that cannot contain the key.

Used by: RocksDB, LevelDB, Cassandra, ScyllaDB, HBase, Pebble, Bigtable.

The core trade-off: read, write, and space amplification¶

The cleanest way to compare engines is three ratios:

The RUM conjecture (Read, Update, Memory — Athanassoulis et al., 2016) states that an access method can optimize at most two of the three at the expense of the third. Every storage engine is a point in that space.

Worked example — where the write cost goes. Update one 100-byte row in a table with two secondary indexes.

• B+Tree (PostgreSQL-style): WAL record (~150 B), plus eventually three 8 KB pages written back (heap + 2 indexes) — about 24 KB of page writes for 100 B of data, though if many updates hit the same hot pages between checkpoints, they share those page writes.
• LSM: WAL record (~150 B) immediately; the entry is later written once at flush, then roughly once per level it is compacted through (each time merged together with other entries into large sequential writes). With 4–5 levels and ~10x per level of overlap, a write amplification of 10–30x is typical — 1–3 KB total, all in large sequential I/O.

Neither is uniformly better. B+Trees win for read-heavy workloads with range queries and moderate writes; LSM trees win for write-heavy workloads, especially on SSDs where they also reduce device wear.

Other designs worth knowing¶

Legacy note: MyISAM¶

MySQL's old default engine had no transactions, no crash-safe recovery, and table-level locks. It is mentioned only because old schemas still use it; InnoDB replaced it as the default in MySQL 5.5.

Choosing¶

• OLTP with mixed reads/writes, secondary indexes, range queries, transactions (users, orders, payments): B+Tree — PostgreSQL or MySQL/InnoDB.
• Write-heavy, mostly append, point reads or recent-range reads (events, logs, time series, messaging, feeds): LSM — Cassandra, ScyllaDB, RocksDB-based stores.
• Embedded storage inside your own service (a queue, a cache with persistence, a metadata store): RocksDB / Pebble (LSM) or LMDB / bbolt (copy-on-write B+Tree).
• Analytics over many rows (sums, group-bys over billions of rows): a column store.

To understand how one of these engines is built from the inside, see the Go storage engine series, which builds an LSM engine step by step.

Common pitfall¶

Assuming an LSM engine's fast writes come for free. The cost is deferred, not eliminated, into compaction, and write amplification from repeated compaction can reach 10–30x the user's write volume. A write-heavy LSM store that looks fast in a short benchmark can saturate disk I/O under sustained load once compaction has to keep pace with incoming writes — at which point the engine stalls foreground writes to let compaction catch up. Benchmarks must run long enough to reach that steady state (often tens of minutes, after the data size exceeds several levels), or they measure only the memtable.