Reading: LSM-Trees vs B-Trees - How Storage Engines Store Data

Notes from the storage chapter of Designing Data-Intensive Applications: the two families of storage engine behind almost every database (log-structured LSM-trees and page-oriented B-trees), how each is built, and why their write paths follow directly from how disks and SSDs behave.

Source: Designing Data-Intensive Applications, Martin Kleppmann, Chapter 3 (Storage and Retrieval)

---

The starting point: an append-only log

The simplest database is two shell functions: set appends key,value to a file, get scans for the last occurrence of the key. Writes are fast (sequential append), reads are O(n).

To speed up reads you add an index: extra metadata derived from the data. Every index slows writes (you update it on each write), so this is the core trade-off of the whole chapter:

Well-chosen indexes speed up reads, but every index slows down writes.

The two engine families answer “how do we keep an index without making writes expensive?” in opposite ways.

         ┌──────────────────────────────┐
         │     How do we update data?   │
         └───────────────┬──────────────┘
         ┌───────────────┴───────────────┐
         ▼                               ▼
Append, never modify            Overwrite in place
(log-structured)                (page-oriented)
LSM-trees: LevelDB, RocksDB,    B-trees: PostgreSQL, MySQL/InnoDB,
Cassandra, HBase, ScyllaDB      SQL Server, Oracle, LMDB

---

Part 1: SSTables and LSM-trees

Hash index first (Bitcask)

Keep an in-memory hash map key → byte offset in the log file. A read is one hash lookup plus one disk seek; a write is one append plus a map update. Fast, but:

• All keys must fit in RAM.
• No range queries (user:100 to user:200 means probing every key).
• The log grows forever, so you need compaction (drop old values for the same key).

SSTable: sort the segment by key

An SSTable (Sorted String Table) is a log segment where the key-value pairs are sorted by key, and each key appears once per segment. That one change gives three wins:

1. Merging is cheap. Merging sorted files is a mergesort-style streaming pass, so it works on files bigger than memory. When a key appears in several segments, the newest wins.
2. A sparse index is enough. You don’t need every key in memory, just one every few KB. To find handiwork, look up the nearest smaller indexed keys and scan a small block.
3. Blocks can be compressed. Records between index entries are scanned together anyway, so compress each block.

Sparse in-memory index              SSTable on disk (sorted)
┌──────────────┬────────┐           ┌─────────────────────────────┐
│ handbag      │ 0      │──────────▶│ handbag : 8784              │
│ handsome     │ 64 KB  │──┐        │ handcuffs: 2133             │
│ hangout      │ 128 KB │  │        │ handful : 4021     ← block 1│
└──────────────┴────────┘  │        ├─────────────────────────────┤
                           └───────▶│ handsome : 1923             │
Find "handiwork":                   │ handwork : 9812     ← block 2│
 1. handbag ≤ handiwork < handsome  │ ...                         │
 2. read block 1, scan it           └─────────────────────────────┘

But how do you write sorted data if writes arrive in random order?

You build the sorted structure in memory first, then flush it. This is the LSM write path:

write(k, v)
    │
    ├──▶ ① append to WAL on disk (sequential; crash recovery only)
    │
    └──▶ ② insert into MEMTABLE (in-memory balanced tree / skip list, sorted)
              │
              │  memtable reaches a few MB
              ▼
         ③ flush as a new SSTable (sequential write, already sorted)
              │
              ▼
       ┌────────────┐  newest
       │ SSTable #4 │
       ├────────────┤
       │ SSTable #3 │
       ├────────────┤
       │ SSTable #2 │  ④ background compaction merges
       ├────────────┤     segments, drops overwritten
       │ SSTable #1 │     and deleted keys
       └────────────┘  oldest

The read path

Check the memtable first, then the newest SSTable, then older ones until the key is found. Reads for keys that don’t exist are the worst case because they touch every segment. The fix is a Bloom filter per SSTable: a tiny in-memory structure that says “definitely not here” or “maybe here”, so most segments are skipped without disk I/O.

read(k) ──▶ memtable ──miss──▶ [Bloom #4?] ──no──▶ [Bloom #3?] ──maybe──▶ SSTable #3 ──hit──▶ value

Deletes and compaction

Segments are immutable, so a delete appends a tombstone marker. It hides older versions of the key until compaction merges them away.

Compaction strategies:

Strategy	Idea	Used by
Size-tiered	Merge newer, smaller SSTables into older, larger ones	Cassandra, HBase (option)
Leveled	Key range split into small SSTables, organized in levels, each ~10x larger than the last; data moves down a level at a time	LevelDB, RocksDB

Leveled compaction

L0  [a-z][a-z][a-z]            ← fresh flushes, may overlap
L1  [a-d][e-h][i-m][n-z]       ← ~10 MB total, non-overlapping
L2  [a-b][c-d][e-f]... (more)  ← ~100 MB total
L3  [................]         ← ~1 GB total
     ▲
     └─ a full level pushes a file down, merging with the overlapping files below

Worked example: one key moving down the levels

Say we write user:42 = "A", later overwrite it with "B", and watch both versions:

① Write "A"      memtable: {user:42=A}
   Flush         L0: [f1: user:42=A, ...]

② Write "B"      memtable: {user:42=B}
   Flush         L0: [f1: user:42=A] [f2: user:42=B]   ← overlap: both files hold the key
                 A read checks f2 first (newest), so it sees B

③ L0 is full → merge f1 + f2 with the overlapping L1 file [u-z]
                 Newest wins, "A" is dropped
                 L1: [u-z: user:42=B]                  ← one version left

④ L1 exceeds its budget → pick [u-z], merge into overlapping L2 files
                 L2: [s-z: user:42=B]
                 If there had been a tombstone for user:42, it would
                 only be discarded here, once no deeper level holds the key

Two things to notice: the old value A is only physically removed when a compaction rewrites the files containing it, and each step touched only the files overlapping that key range, not the whole database.

Where the name comes from

Log-Structured Merge-tree: writes are logged (appended), and sorted runs are merged in the background. Lucene (Elasticsearch, Solr) uses the same idea for its term dictionary.

---

Part 2: B-trees

The B-tree (1970) is the default index in nearly every relational database. It shares one idea with SSTables, data sorted by key, but is organized differently.

Fixed-size pages, not variable-size segments

A B-tree breaks the database into fixed-size pages (traditionally 4 KB, now often 8 to 16 KB) and reads or writes one page at a time. That mirrors the hardware: disks are also divided into fixed-size blocks.

Pages refer to each other by on-disk page number, like pointers but on disk, forming a tree:

                 ┌─────────────────────────────────────┐
ROOT PAGE        │  ·  100  ·  200  ·  300  ·  400  ·  │
                 └──┬─────┬──────┬──────┬──────┬───────┘
      keys < 100 ───┘     │      │      │      └─── keys ≥ 400
                          ▼      ...
              ┌─────────────────────────────┐
INTERIOR      │  ·  125  ·  150  ·  175  ·  │      key ranges between
PAGE          └──┬──────┬───────┬───────┬───┘      the references
                 │      │       │       │
                 ▼      ▼       ▼       ▼
             ┌──────┐┌──────┐┌──────┐┌──────┐
LEAF PAGES   │ 100  ││ 125  ││ 150  ││ 175  │      leaves hold the actual
             │ 105  ││ 130  ││ 155  ││ 180  │      values (or a pointer
             │ 112  ││ 141  ││ 163  ││ 192  │      to where they live)
             └──────┘└──────┘└──────┘└──────┘

• Lookup: start at the root, follow the child whose key range contains your key, until you hit a leaf.
• Branching factor: the number of child references per page (often hundreds). A tree four levels deep with 4 KB pages and a branching factor of 500 stores up to ~250 TB, so lookups take only a handful of page reads.

Updates overwrite in place

Updating a value finds the leaf page and overwrites that page on disk. The references to the page stay valid. This is the sharp contrast with LSM-trees, which never modify a file once written.

Inserts and page splits

Inserting a key into a full page splits it into two half-full pages and updates the parent to point to both. This keeps the tree balanced: depth stays O(log n).

Insert 133 into a full leaf [125 130 141 145]

BEFORE                                   AFTER
Parent:  ·  125  ·  150  ·               Parent:  ·  125  ·  141  ·  150  ·
            │                                        │       │
            ▼                                        ▼       ▼
        [125 130 141 145]  full         [125 130 133]     [141 145]
                                         two half-full pages

Making B-trees crash-safe: the WAL

A split touches several pages (the two leaves plus the parent). If the DB crashes midway you get an orphan page or a corrupted tree. So B-trees add a write-ahead log (redo log): an append-only file where every modification is written before it is applied to the tree pages. After a crash, replay the WAL to restore consistency.

Other B-tree details:

• Latches (lightweight locks) protect the tree for concurrent access.
• Some systems (LMDB) use copy-on-write instead of a WAL: a modified page is written to a new location and a new parent chain is created. This also helps snapshot isolation.
• Optimizations: abbreviated keys in interior pages (higher branching factor), leaf pages laid out sequentially, sibling pointers for range scans.

---

Side-by-side

                   LSM-TREE                            B-TREE
Write path    memtable → WAL → flush SSTable      find leaf page → overwrite page (+ WAL)
I/O style     sequential, append-only             random, in-place
Files         immutable                           mutable pages
Reorganize    background compaction               page splits on insert
Data layout   sorted runs across levels           one sorted tree
Missing key   may check many segments (Bloom)     one root-to-leaf walk

	LSM-tree	B-tree
Write throughput	Usually higher: sequential writes, compressed, less fragmentation	Lower: each write goes to the WAL and to the page (and to a split page sometimes)
Read performance	Slower: may check several structures	Faster and more predictable: one location per key
Write amplification	One logical write becomes several physical writes over time (compaction)	One logical write becomes WAL + page write(s)
Space	Compresses better; no page fragmentation	Pages partly empty after splits
Latency predictability	Compaction can steal disk bandwidth and cause p99 spikes	More predictable
Locking / transactions	Key can exist in multiple segments	Each key lives in exactly one place, so range locks attach to the tree easily
Typical fit	Write-heavy, large ingest: time series, event logs, messaging	Read-heavy OLTP, strong transactional semantics

Gotchas the book calls out

• Compaction can starve reads/writes. Disk bandwidth is finite. If ingest outpaces compaction, segments pile up and reads degrade, and many LSM engines don’t throttle incoming writes by default, so watch it.
• Write amplification is the real cost metric. Both engines write more bytes than the application asked for. On SSDs this also wears the drive.
• Benchmarks lie across workloads. Always test on your data and access pattern.

---

How hardware shapes the design

Both designs are shaped by one constraint: sequential access is far cheaper than random access on storage media.

Medium	Why it matters
HDD	A random access needs a mechanical seek (~ms). Sequential throughput is 100x+ better. LSM’s appends and merges are tuned for this.
SSD	No seek, but flash can’t overwrite a cell in place: it must erase a whole block (hundreds of KB to MBs) before writing. The firmware’s flash translation layer hides this by remapping pages and doing its own garbage collection. Small random in-place writes therefore cause extra internal writes. LSM’s large sequential writes fit this well; B-tree in-place updates are what the SSD has to work around.
RAM	Memtable and Bloom filters live here. The DB must rebuild them from the WAL or SSTables on restart.

• Page size ≈ block size. B-tree pages are sized to match disk blocks so one page read is one I/O.
• Large flushes. An LSM memtable flush writes megabytes at once, the pattern both disks and SSDs prefer.
• Why Bloom filters exist. A disk read is millions of times slower than a RAM check, so spending memory to avoid I/O is a good trade.
• Why WALs are everywhere. Even in-place structures need one cheap sequential write to be durable.
• Why fsync matters. Data in the OS page cache is lost on power failure. The WAL must be flushed for the durability guarantee.

---

Takeaways

1. An LSM-tree turns random writes into sequential ones by buffering in memory and flushing sorted, immutable files, and pays for it with compaction and slower, multi-place reads.
2. A B-tree keeps a single sorted tree of fixed-size pages updated in place, so reads are predictable, and pays with random writes, page splits and a WAL.
3. Neither wins universally: choose by workload (write-heavy ingest vs. read-heavy transactions), and measure write amplification and tail latency, not just throughput.
4. The shape of each engine follows the hardware: sequential I/O is cheap, and flash can’t overwrite in place.