Storage Engines: Logs, LSM-Trees, and B-Trees
Module 2 · Storage and Encoding

Storage Engines: Logs, LSM-Trees, and B-Trees

Build intuition for how databases store and find data, from an append-only log with a hash index to LSM-trees and B-trees, and weigh their trade-offs in write amplification, read cost, and crash safety.

The Simplest Database

Here’s a working key-value store in two shell functions:

db_set () { echo "$1,$2" >> database; }
db_get () { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1; }

Writes are fast: appending to a file is about the cheapest disk operation there is. Reads are terrible: every lookup scans the whole file. Real storage engines are mostly clever answers to one question: how do we keep writes cheap while making reads fast?

The answer is an index: extra structure derived from the data that speeds up reads. Every index speeds up some reads and slows down writes, because it must be updated too. That’s the fundamental trade-off.


Step 1: Append-Only Log + Hash Index

Keep appending records to a log file, and keep an in-memory hash map from each key to the byte offset of its latest value.

  • Write: append to the file, update the offset in the map.
  • Read: look up the offset, seek, read one record.

Problems to solve:

  • The file grows forever. Split the log into segments, and periodically compact them: rewrite each segment keeping only the latest value per key, then merge segments.
  • Deletes: append a special tombstone record; compaction drops the key.
  • Crashes: rebuild the hash map by scanning segments on restart (or snapshot it).
  • Limits: all keys must fit in memory, and range queries (“all keys between A and F”) need a full scan.

Append-only design is fast because sequential writes beat random writes, and it makes crash recovery simpler because old data is never overwritten in place.


Step 2: Sorted Segments and LSM-Trees

Now require each segment to be sorted by key. A sorted segment is often called an SSTable (sorted string table). Sorting buys a lot:

  • Merging segments is an efficient merge-sort pass.
  • The in-memory index can be sparse: one entry every few kilobytes, since you can scan forward from the nearest known key.
  • Range queries become efficient.

But writes arrive in random order. How do you produce sorted files? Buffer writes in a sorted in-memory structure first:

  1. 1 WAL

    Append for crash safety

  2. 2 Memtable

    Sorted, in memory

  3. 3 Flush

    Write as sorted SSTable

  4. 4 Compact

    Merge, drop old values

  1. Every write is appended to a write-ahead log (so it survives a crash) and inserted into the memtable, a sorted in-memory tree.
  2. When the memtable gets big, it’s written to disk as a new SSTable.
  3. Reads check the memtable, then the newest SSTable, then older ones.
  4. Background compaction merges SSTables and discards overwritten and deleted values.

This is the log-structured merge-tree (LSM-tree) design used by engines such as RocksDB, LevelDB, Cassandra, and HBase. To avoid checking many files for keys that don’t exist, LSM engines use Bloom filters: compact probabilistic structures that can say “definitely not here.”


Step 3: B-Trees

The other major family, and the default in most relational databases, is the B-tree. It’s been the standard index structure since the 1970s.

  • Data is organized into fixed-size pages (often 4–16 KB) on disk.
  • Pages form a tree. Each page holds sorted keys and pointers to child pages covering key ranges. Leaf pages hold values or references to rows.
  • A lookup walks from the root to a leaf: with a branching factor of a few hundred, a few levels cover billions of keys.
  • Updates happen in place: find the leaf page, overwrite it. If a page fills up, split it into two and update the parent.
Looking up key 251: three page reads from root to leafunder 100100–199200–299300+root page200–239240–269270–299internal page248249251255260leaf pageUpdates overwrite the leaf in place; a full page splits and updates its parent.

Because a page split modifies several pages, a crash mid-update could corrupt the tree. B-trees also use a write-ahead log so that every change is first recorded durably and can be replayed after a crash.


LSM vs. B-Tree

LSM-treeB-tree
WritesSequential appends; typically higher write throughputRandom in-place page writes
ReadsMay check several files; Bloom filters helpPredictable: one path root to leaf
Write amplificationData rewritten repeatedly during compactionWhole pages rewritten for small changes, plus the WAL
SpaceCompresses well; fragmentation removed by compactionSome unused space in pages
Latency spikesCompaction can compete with foreground workGenerally steadier
Transactions and lockingPossible, more variedNatural: each key lives in one place

Write amplification (one logical write causing several physical writes) matters for both throughput and SSD wear. Neither design wins everywhere. Measure with your workload.

⚠️ Common Pitfall: Ignoring Compaction Until Production

Common mistake: benchmarking an LSM-based database for an hour, seeing great write throughput, and going live.

Under sustained load, compaction may fall behind. Unmerged files pile up, reads slow down, and disk usage climbs. Benchmark long enough for compaction to reach a steady state, and monitor pending compaction in production.


Other Index Ideas in Brief

  • Secondary indexes map a non-key column to the rows that have it; values may repeat.
  • Clustered indexes store rows inside the index itself; covering indexes include extra columns so some queries never touch the table.
  • Multi-column and spatial indexes handle queries over several dimensions, such as latitude and longitude.
  • In-memory databases are fast not only because RAM is fast, but because they avoid encoding data for disk.
🧪 Try It: Build a Tiny Log-Structured Store

In any language, in under 100 lines:

  1. Append key,value lines to a file and keep a hash map from key to byte offset.
  2. Implement get with a seek instead of a scan.
  3. Add tombstones for deletes.
  4. Write a compaction function that rewrites the file keeping only the latest value per key.
  5. Kill the process mid-write. What does recovery need to handle?
🧠 Knowledge Check

1. What's the core trade-off of adding an index?

2. In an LSM engine, what is the memtable?

3. Why do B-trees also use a write-ahead log?

Up Next

The next lesson covers analytical storage and how data is encoded so systems can evolve without breaking each other.