# B-Trees vs LSM-Trees: The Storage Engine Tradeoff

> Every database picks one of two ways to put data on disk. The choice between B-trees and LSM-trees is really a choice about whether you optimize for reads or writes — and you can't have both for free.

URL: https://harshith.in/blog/btree-vs-lsm-tree/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: databases, systems, performance

Postgres uses B-trees. RocksDB, Cassandra, and LevelDB use LSM-trees. They're
solving the same problem — store key-value data on disk and find it again — but
they make opposite bets about which operation deserves to be fast.

## The B-Tree: Update in Place

A B-tree keeps keys sorted in fixed-size pages, with a shallow, high-fanout tree
on top. A lookup walks from root to leaf — a handful of page reads even for huge
datasets:

```text
            [ 25 | 50 | 75 ]            ← root
           /     |     |    \
     [..20] [30..45] [55..70] [80..]    ← leaves hold the data
```

Reads are excellent: the tree is shallow and a key lives in exactly one place.
The cost is writes. To insert, you find the right leaf and **modify it in
place** — a random write. Pages split when they fill, and the write-ahead log
has to durably record the change first. Lots of small random I/O.

## The LSM-Tree: Never Modify, Always Append

A log-structured merge tree refuses to do random writes. New data goes into an
in-memory table; when it fills, it's flushed to disk as an immutable sorted file
(an **SSTable**). Writes are sequential and fast:

```text
   writes ──▶ [ memtable ]  (in RAM, sorted)
                  │ flush when full
                  ▼
           [ SSTable L0 ] [ SSTable L0 ] ...
                  │ background compaction merges + sorts
                  ▼
           [ SSTable L1 .................. ]
```

The catch is reads. A key might be in the memtable, or any of several SSTables.
A lookup may have to check multiple files — softened by Bloom filters and an
index per file, but still more work than a B-tree's single path.

## The Amplification You're Trading

Three costs frame the whole decision:

- **Read amplification** — extra reads per lookup. B-tree: low. LSM: higher
  (multiple SSTables).
- **Write amplification** — bytes actually written per byte of data. B-tree:
  page rewrites + WAL. LSM: compaction rewrites data repeatedly across levels.
- **Space amplification** — disk used per byte of live data. LSM keeps stale
  copies until compaction; B-trees leave half-empty pages.

```text
              reads      writes     space
   B-tree     fast       slower     fragmented
   LSM-tree   slower     fast       stale until compacted
```

## Picking a Side

- **Read-heavy, point lookups, transactional** → B-tree. This is most relational
  workloads, which is why Postgres and MySQL's InnoDB use them.
- **Write-heavy, high ingest, time-series, logs** → LSM-tree. Sequential writes
  and cheap appends win when you're firing data in faster than you read it.

Neither is "better." Compaction tuning is the LSM's eternal headache; write
amplification and vacuum are the B-tree's. You're choosing which problem to own.

## Takeaways

- B-trees update in place: great reads, random-write cost.
- LSM-trees append immutable sorted files: great writes, multi-file read cost
  plus background compaction.
- The real axis is read vs write amplification — pick the engine that matches
  whether your workload reads or writes more.