LSM-Tree vs B-Tree: How Databases Store Data on Disk
Why is one database great for writes and another for reads? The storage engine — B-tree (in-place, read-optimized) vs LSM-tree (append-only, write-optimized), compaction, Bloom filters, and read/write amplification.
🟠Fundamentals · Senior → 🔴 super-senior deep dive
Ever wondered why PostgreSQL and Cassandra feel so different, or why one database is "great for writes" and another "great for reads"? A huge part of the answer is the storage engine underneath — specifically, whether it uses a B-tree or an LSM-tree to lay data on disk. This is the kind of internals question that marks a senior/staff engineer. Let's unpack both from first principles and see exactly what trade-off each one makes.
The problem both solve
A database has far more data than fits in RAM, so it lives on disk, and disks are slow at random access. Both structures exist to organise data on disk so you can find a key quickly and keep it sorted for range scans — they just take opposite strategies to do it.
B-tree: update in place
The B-tree (used by MySQL/InnoDB, PostgreSQL, and most classic relational DBs) is a balanced tree of fixed-size pages. To find a key you walk from the root down through a few levels to the leaf — just 3–4 disk reads even for billions of rows, because the tree is wide and shallow. To update a value, you find its page and overwrite it in place.
🟠Strengths: reads are fast and predictable (a bounded number of page reads), and range queries are natural because leaves are sorted and linked. Weakness: writes scatter. Updating random keys means seeking to random pages and rewriting them — lots of random I/O — and to stay crash-safe most B-trees also write to a write-ahead log first, so a single logical write touches disk more than once.
LSM-tree: only ever append
🔴 The LSM-tree (Log-Structured Merge tree — used by Cassandra, RocksDB, LevelDB, HBase, ScyllaDB) flips the strategy: never do random writes. Here's the flow:
- A write goes into an in-memory sorted table (the memtable) — instantly fast, no disk seek.
- When the memtable fills, it's flushed to disk as an immutable sorted file called an SSTable. Writes are purely sequential appends — the disk's favourite pattern.
- Updates and deletes don't modify old files; they write a new value (a delete is a marker called a tombstone). The newest value wins.
- A background process called compaction periodically merges SSTables, dropping superseded values and tombstones to reclaim space and keep reads sane.
🔴 Strengths: writes are extremely fast because they're sequential and in-memory first — LSM-trees shine for write-heavy and high-ingest workloads (time-series, event logs, feeds). Weakness: a read might have to check the memtable and several SSTables to find the latest value (read amplification). The fix is a Bloom filter per SSTable — a tiny structure that answers "is this key definitely NOT here?" so reads skip files that can't contain the key. Compaction also costs background I/O (write amplification).
The two amplifications (the senior vocabulary)
🔴 Name these and you sound like you've tuned a database:
- Write amplification: one logical write causes several physical writes (compaction rewrites data repeatedly). LSM-trees trade this for fast ingest.
- Read amplification: one logical read touches multiple places (several SSTables). Bloom filters and compaction keep it in check.
- Space amplification: old superseded values linger until compaction removes them.
B-trees have low read amplification but do more random write I/O; LSM-trees have low write cost but higher read and compaction overhead. There's no free lunch — you're choosing which one to pay.
Side by side
| B-tree | LSM-tree | |
|---|---|---|
| Writes | Slower (random, in-place) | Very fast (sequential append) |
| Reads | Fast, predictable | Slower (multiple files) |
| Best for | Read-heavy, OLTP, ranges | Write-heavy, high ingest |
| Used by | MySQL, PostgreSQL | Cassandra, RocksDB, HBase |
The interview-ready summary
"It's a read-vs-write trade-off in the storage engine. B-trees update in place — a few page reads per lookup, so reads are fast and predictable, but random writes cost I/O; great for read-heavy OLTP like MySQL/Postgres. LSM-trees only append: writes hit an in-memory memtable then flush to immutable SSTables, with background compaction merging them — so writes are extremely fast, at the cost of read amplification that Bloom filters mitigate; great for write-heavy systems like Cassandra. If my workload is ingest-heavy, I'd pick an LSM engine; if it's read- and range-heavy, a B-tree." That's exactly the depth the question is probing for.
What to read next
- Bloom Filters — the structure that makes LSM reads fast
- Database Indexing — how these trees power indexes
- SQL vs NoSQL — the engines above map onto this split
- ← The complete System Design guide (hub)
