LSM trees vs B-trees

The most interesting interview answer you can give about database internals is the one that doesn't pretend the choice of on-disk data structure is settled. For the first thirty years of databases there was effectively one answer — B-trees — because that's what Postgres, MySQL, Oracle, and SQL Server all shipped. Then around 2010 a parallel family started winning at the workloads B-trees were worst at: Cassandra, RocksDB, LevelDB, and eventually the storage layers under TiDB, CockroachDB, and ScyllaDB all picked the other shape, the LSM tree. Today the right answer to "which storage engine should I use" depends on the workload, and understanding the two shapes is what lets you give that answer with confidence.

The reason both shapes exist — instead of one obviously winning — is that they make exactly opposite trade-offs. A B-tree is optimized for the worst case where you mutate a random row deep in the dataset and then read it back. An LSM tree is optimized for the worst case where you write twenty thousand rows per second and your reads can tolerate looking in more than one place. Production workloads vary along that axis, which is why the engine choice is workload-dependent rather than universal.

The shape of a B-tree

A B-tree is a balanced, sorted tree of fixed-size pages (8 KB in Postgres, 16 KB in InnoDB) stored on disk. Each interior page holds keys and pointers to child pages; each leaf page holds the actual rows in sorted key order. Reading a row is a walk from root to leaf — typically 3-4 pages deep on a table with hundreds of millions of rows. If those pages are in the buffer pool, the walk is microseconds. If they're not, each page miss is a disk seek (a few ms on SSD, much more on HDD).

Writes work by finding the right leaf page, modifying it in place, and writing the change to the WAL first (see [CONCEPT]write-ahead-log). The mutation cost is dominated by the random I/O to fetch the page if it's cold. If the leaf page splits because there's no room for the new key, the parent page also has to be modified, and so on up the tree — most inserts touch one page, but a small fraction touch several.

The properties that fall out of this design:

• Predictable read latency. Three or four page reads, period.
• Range scans are fast. Leaves are already sorted; you just walk left-to-right.
• Random writes are expensive. Each write touches a pseudo-random page; SSDs hate the random I/O pattern at scale.
• Space overhead is moderate. Page splits leave half-full leaves; B-trees typically run at 60-70% page fill rate, so about 30-50% overhead vs the raw data size.

The shape of an LSM tree

An LSM tree (Log-Structured Merge tree) flips the whole model. Writes don't touch disk at all initially. They go to:

1. The WAL, for durability (in case of crash).
2. An in-memory memtable — typically a sorted skip list.

When the memtable hits a size threshold (say 64 MB), it's frozen and a new empty memtable takes over for incoming writes. The frozen memtable is then flushed to disk as an immutable SSTable (Sorted String Table) file. This flush is sequential I/O — fast, even on HDD.

The catch is that now reads have to check both the memtable and every SSTable on disk to find the latest value for a key. Without help, that means N SSTables = N times the read cost. LSM engines mitigate this with:

• Bloom filters per SSTable that say "this SSTable definitely doesn't contain key X" (false positives possible, false negatives impossible). A bloom filter check is a few hash lookups; it lets the engine skip 99% of SSTables for most reads.
• Compaction — a background process that merges old SSTables into newer ones, reducing N over time. Compaction is the price of the LSM design: every byte gets rewritten several times over its lifetime, which is called write amplification.

The properties:

• Insanely fast writes. Memtable writes are RAM-speed; SSTable flushes are sequential I/O. LSM stores can sustain 100K+ writes/sec on commodity hardware.
• Variable read latency. Bloom filters help, but reads still sometimes hit multiple SSTables. Worst-case p99 reads can be much slower than B-tree reads.
• Compaction tail latency. When compaction kicks in, it competes for I/O with foreground traffic. Production LSM deployments care a lot about scheduling compaction to avoid stalls.

The trade-off table, with real numbers

The biggest single trade-off is write amplification. A B-tree rewrites each page once per logical write (roughly). An LSM tree rewrites the same data 5-30 times over its lifetime as it gets compacted from level 0 down to level N. On premium SSD that's fine; on cheap storage or write-endurance-limited hardware, the LSM tax matters.

Working the write-amplification number

"5-30×" is abstract until you put bytes behind it. Take a leveled LSM (RocksDB-style) where each level is ~10× the size of the one above, and a write has to get compacted from level 0 all the way down to level 6. Every time a byte moves down a level, it gets read, merged, and rewritten — that's one unit of write amplification per level it passes through:

So one logical 1 KB write becomes ~8 KB of physical writes — and that's a well-behaved leveled LSM. Now run it forward: at 50K writes/sec × 1 KB, that's 50 MB/s of logical writes but ~400 MB/s of physical SSD writes. On a consumer SSD rated for ~600 TBW (terabytes written) of endurance, sustained 400 MB/s burns the warranty in roughly 17 days of continuous write. This is why high-write LSM fleets run on datacenter SSDs rated for full-drive-writes-per-day, and why "just turn up the write rate" is never free.

A B-tree on the same workload writes ~1.5× — about 75 MB/s physical — and would take five times longer to wear the same drive. But it caps out far below 50K random writes/sec in the first place, so you rarely get to make the comparison fairly.

Which one wins for which workload

The honest decision rule, after watching teams pick:

• Read-heavy with frequent point lookups (user profiles, product catalogs, configuration stores): B-tree wins. Reads are predictable; the write rate is well within B-tree's comfort zone.
• Write-heavy time-series or log ingest (metrics, events, audit logs, telemetry): LSM wins. Append-only access matches the LSM design; the variable read latency is acceptable for queries that scan windows of time.
• Mostly-immutable append data (event-sourcing, change logs, immutable history): LSM. Compaction is minimal because there's nothing to merge.
• Mixed OLTP with strict p99 latency (banking, e-commerce checkout): B-tree. The compaction-induced tail latency in an LSM can violate SLA.
• Cassandra-scale (millions of writes/sec): LSM, because no B-tree implementation gracefully scales that high on commodity hardware.

The hybrid systems blur the line

The real world isn't pure B-tree or pure LSM. WiredTiger (MongoDB's storage engine) is technically a B-tree but uses copy-on-write instead of in-place updates, giving it LSM-ish write characteristics. ScyllaDB tunes its LSM compaction so aggressively (and shards compaction work across cores) that read latency feels almost B-tree-like. Postgres has HOT updates that avoid full leaf modification for non-indexed column changes, narrowing the random-write gap.

The takeaway isn't that B-tree or LSM is "better" — it's that both designs have evolved enough that the right engine for your workload exists, and the wrong one will cost you 10x more infrastructure than it should.

A war story about the wrong engine

A team I worked with stored IoT telemetry — sensor readings, roughly 100K events/sec at peak — in a Postgres table with an index on (device_id, timestamp). It worked for a year. Then the device fleet doubled and the database started missing its write SLA: foreground writes were waiting 2-5 seconds for checkpoint I/O to clear, the buffer pool was churning between hot pages, and adding indexes for new query patterns made it worse because each index slowed every write.

The eventual fix was migrating the telemetry table to TimescaleDB hypertables (which use B-trees internally but add time-based partitioning to keep individual indexes small) and the high-volume sensor-reading table to ClickHouse (column store, LSM-like write path). After migration, the same workload on smaller hardware was 10x faster on writes and the read patterns the analytics team cared about (window scans over time ranges) got faster too.

The lesson is that the engine you pick is often a bigger performance lever than any amount of tuning the wrong engine. "It's a database, we have one already" is a reasonable starting position; "the database isn't the right shape for our workload" is a reasonable migration decision when the numbers say so.

When the choice doesn't matter

Three cases where the engine question genuinely doesn't matter much:

• Small data (under 100 GB). Both engines fit in RAM; the on-disk shape is largely academic.
• Read-only or near-read-only. Both are fast for reads; the difference is in write throughput, which you barely use.
• You're using a managed database (RDS, DynamoDB, Cloudflare D1). The engine is picked for you; the only decision left is which service.

For everything else — anything write-heavy, anything at scale, anything where the database is on the critical path of latency — the engine choice is real and worth thinking about up front.

[CONCEPT]write-ahead-log appears in BOTH families — it's how durability is implemented regardless of the on-disk shape. [CONCEPT]indexes-deep-dive is what determines which keys benefit from each engine's strengths. [CONCEPT]replication is the layer above this — both LSM and B-tree systems ship WAL records to followers.