Storage Engines: B-Trees vs. LSM-Trees

The two dominant strategies for turning a stream of writes into something you can read back efficiently.

At the bottom of every database is an index deciding how data actually sits on disk. Almost every general-purpose storage engine is built around one of two families: B-Trees, which update pages in place, or LSM-Trees, which never overwrite — they only append.

Toggle between the two below to see how the same write is handled completely differently.

Fig. 3 — Write path: B-Tree vs. LSM-Tree

Click a node for details.

Every write updates a page in place — reads stay fast and predictable, but each write costs a random disk access.

B-Trees

A B-Tree breaks the database into fixed-size pages (traditionally 4 KB, matching a disk block) arranged in a tree. To update a value, the engine finds the right leaf page and overwrites it in place. To survive a crash mid-write, every write is first appended to a write-ahead log (WAL) — if the database restarts mid-update, it replays the WAL to restore the page to a consistent state.

This gives predictable read performance (a lookup is always roughly O(log n) page reads) at the cost of write amplification: every update is a random disk write to an existing page.

LSM-Trees

A log-structured merge-tree never updates in place. Writes go into an in-memory sorted structure (the memtable), backed by the same kind of append-only WAL for durability. When the memtable fills up, it’s flushed to disk as an immutable, sorted file — an SSTable (Sorted String Table). Over time, a background compaction process merges SSTables together, discarding overwritten and deleted keys.

The result: writes are always sequential and fast, since you’re only ever appending. The tradeoff shifts to reads (which may need to check the memtable and several SSTables before finding the latest value) and to compaction, which consumes background I/O.

# Simplified LSM write path
1. append(key, value) -> WAL           # durability
2. memtable.insert(key, value)         # fast, in-memory
3. if memtable.size > threshold:
     flush memtable -> new SSTable      # sequential disk write
     memtable = new empty memtable
4. background: compact(sstables)        # merge, drop stale/deleted keys