Storage Engines: LSM-trees vs B-trees

Retrieve before reading

In one sentence: a database that only ever appends to a file has the fastest possible writes. Why is that not the whole story?

The simplest database, and the trade-off it exposes

Start with the world's simplest key-value store: a text file where every write appends a line "key,value", and every read greps the file for the last occurrence of the key. Writes are as fast as a file can be - appending is the simplest possible write operation, and many real databases use an append-only log (an append-only sequence of records) as their foundation. But reads are O(n): double the records, double the scan time.

The fix is an index: additional metadata, derived from the primary data, that acts as a signpost to where the data lives. And here is the trade-off that frames the entire chapter: an index speeds up reads, but every index slows down writes, because the index must be updated on every write. That is why databases do not index everything by default - you choose indexes based on your query patterns, and you pay for each one on every write.

Hash indexes: the simplest index

Keep an in-memory hash map from key to byte offset in the append-only file. Write: append, then update the map. Read: look up the offset, seek, read. This is essentially what Bitcask (Riak's default engine) does. It is excellent when there are many writes per key but not too many distinct keys - the book's example is a per-video play counter, where the key is the video URL and the value is incremented constantly.

To keep the file from growing forever, break it into segments and run compaction in the background: throw away duplicate keys, keeping only the most recent value per key, and merge segments. Segments are immutable once written, so merging never disturbs live reads and writes. The hash index has two hard limits: the hash map must fit in memory (all keys in RAM), and range queries are hopeless - fetching every key between kitty00000 and kitty99999 means one lookup per key.

SSTables and LSM-trees: sorted segments

Now make one small change to the segment format: require the key-value pairs to be sorted by key. This is a Sorted String Table, or SSTable. Sorting seems to break sequential writes, but the trick is to sort in memory first:

• Writes go into an in-memory balanced tree (a red-black tree, say) called the memtable.
• When the memtable passes a threshold (a few MB), flush it to disk as an SSTable - the tree already holds the keys sorted, so the flush is sequential.
• Reads check the memtable first, then the newest segment, then older segments.
• Background compaction merges segments, discarding overwritten and deleted values.

Sorted segments buy three things. First, merging is mergesort: read the input files side by side, copy the lowest key, repeat - and when the same key appears in several segments, keep the value from the most recent one. Second, the in-memory index can be sparse: one key per few kilobytes of segment is enough, because you can seek to a nearby key and scan forward. Third, since range reads scan consecutive keys anyway, you can group records into blocks and compress them - disk bandwidth is usually scarcer than CPU, so spending CPU to shrink what hits the disk is a good trade.

This family is the Log-Structured Merge-Tree (LSM-tree), named by Patrick O'Neil and colleagues. LevelDB and RocksDB implement this family as embedded storage-engine libraries; Cassandra and HBase use similar designs influenced by Google's Bigtable paper, which introduced the terms "SSTable" and "memtable". Lucene, the search engine inside Elasticsearch and Solr, uses the same idea for its term dictionary. One practical wrinkle: a read for a key that does not exist must check the memtable and every segment before concluding - so LSM engines keep a Bloom filter in memory, a compact structure that can say "this key is definitely not here" and skip the disk reads.

B-trees: the incumbent

The most widely used index is not log-structured at all. The B-tree, introduced in 1970, keeps keys sorted like an SSTable, but with a completely different philosophy: instead of variable-size segments written sequentially, it breaks the database into fixed-size pages (traditionally 4 kB) and reads or writes one page at a time - matching how the disk itself is arranged. Each page holds keys and references to child pages; the root page's keys are the boundaries between child ranges. A lookup walks from root to leaf, following the range that contains the key, in O(log n) pages. A page that fills up is split in two, and the parent is updated - the tree stays balanced by construction.

The defining difference is the write operation: a B-tree overwrites a page in place, while an LSM-tree only appends. Overwriting in place is dangerous when a single logical operation touches several pages - a page split writes two new pages and the parent, and a crash halfway leaves a corrupted index. So B-tree implementations keep a write-ahead log (WAL, or redo log): every modification is appended to the WAL before the pages are touched, and after a crash the WAL replays the tree back to a consistent state. The cost: every write hits the disk at least twice - once to the log, once to the page.

LSM vs B-tree: the comparison

The rule of thumb: LSM-trees are faster for writes, B-trees are faster for reads - and real benchmarks are workload-sensitive, so the honest answer is "benchmark your own workload". The mechanism behind each side:

• Write speed: an LSM turns every random write into sequential appends and background merges, which is why it sustains much higher write throughput. The cost is write amplification - one logical write causes many physical writes over the segment's lifetime, which matters on SSDs that wear out.
• Read speed and predictability: a B-tree stores each key in exactly one place, so reads are predictable. An LSM's compaction runs in the background and competes for disk bandwidth; average latency stays fine, but high percentiles (p99) can spike while a big merge is running.
• Transactions: because each key lives in exactly one place, B-trees make range locking natural - which is why relational databases that offer strong transaction isolation (the subject of lesson 0006) tend to use them.

There is no universal winner. Newer datastores increasingly choose log-structured engines; the relational incumbents stay on B-trees; and the book's advice is to test empirically with your own workload rather than argue from principle.

Problem set