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.