Storage Engine Comparison: B+ Tree vs LSM Tree
Two ways to organise bytes on disk: keep one sorted structure and update it in place, or append sorted runs and merge them later. Neither is better. Each is the right answer to a different workload, and the comparison is a table of dimensions, not a verdict.
Why this exists
The mechanism as the answer to a problem — read this before the name.
- Problem
A team is choosing storage for a new service: an ordering system with hot rows and range reports, or an event pipeline with a million appends per minute. "Which engine is better?" is the wrong question; the right one is which costs each workload can carry.
↓ - Naive solution
Pick the engine with the best published benchmark, or the one everyone uses.
↓ - Why it breaks
Published numbers are for someone else's workload. A B+ tree that wins point reads by 20% loses ingest by 10×; an LSM that wins ingest loses range scans by the number of runs it must merge. The team ships an engine tuned for the wrong shape and discovers it at scale.
↓ - Better idea
Compare the two designs dimension by dimension — point reads, range scans, write cost, compaction versus splits, caching, the three amplifications, concurrency, fragmentation — and score each for the actual workload.
↓ - Internal mechanism
B+ tree: one sorted structure of fixed-size pages, updated in place, split on overflow, protected by latches, buffer pool and WAL. LSM: append-only WAL, sorted memtable, immutable sorted files per level, bloom filters, background compaction. The same logical operations map to very different physical work.
↓ - Trade-offs
B+ tree: best point and range reads, in-place updates that keep hot pages hot, page-granular write amplification, fragmentation over time. LSM: sequential writes at disk bandwidth, excellent compression, multi-run reads mitigated by bloom filters, compaction that competes for I/O and can stall.
↓ - Real database
B+ trees: PostgreSQL, MySQL/InnoDB, SQLite, Oracle, SQL Server. LSM trees: RocksDB, LevelDB, Cassandra, ScyllaDB, HBase. Hybrids: MyRocks (LSM under MySQL), WiredTiger (both layouts under MongoDB), TiKV and CockroachDB (RocksDB/Pebble under a SQL layer).
Choose your depth
The same mechanism at four altitudes. Start where you are; come back deeper.
A B+ tree keeps every row in its sorted place and changes it there; reads are a short descent, writes touch the page where the row lives. An LSM tree never changes a file; writes are appended and sorted in memory, files are merged in the background, and reads look in several places.
Relational databases are B+ trees because their workloads are read-heavy with hot updates and range queries. Wide-column and key-value stores are LSM trees because their workloads are ingest-heavy. Both are correct.
Two answers to "where does the row go?"
The B+ Tree Internals: Pages, Splits, Merges lesson built a structure in which every key has one place: descend from the root, find the leaf, and the row is there or it is nowhere. Writes go to that place; if the page is full it splits. The LSM Trees: Why Some Engines Favour Writes lesson built the opposite: a key has as many places as it has versions, the newest version is authoritative, and the engine converges on one place only through compaction. Every dimension in the comparison below follows from that single difference — in-place versus append-and-merge.
It is tempting to read the table as a scorecard. Resist it. The columns are answers to different questions, and the Write, Read and Space Amplification lesson showed why a workload mix flips the ranking: the RUM triangle guarantees each design is losing somewhere.
The comparison
Each row names the mechanism behind the verdict, because the mechanism is what transfers to the next engine you meet. "B+ tree wins range scans" is trivia; "one linked sorted run versus a merge across every overlapping run" is understanding.
| Dimension | B+ tree (PostgreSQL, InnoDB, SQLite) | LSM tree (RocksDB, Cassandra, HBase) |
|---|---|---|
| Point reads | root → branch → leaf, upper levels cached: ≈ 1 disk read | memtable + bloom check per candidate file: ≈ 1.06 block reads; absent keys nearly free |
| Range scans | follow the leaf chain: one sorted run, sequential | merge L0 files + one run per level, skip tombstones: 7–36 runs |
| Write-heavy workloads | random updates dirty a page per row; checkpoint writes 8 KB pages | sequential WAL append + memtable; flush 64 MB at a time |
| Compaction | none | background k-way merge; can lag and stall writes; competes for I/O |
| Page splits | on leaf overflow: two half-full pages, local and bounded | none — files are immutable |
| Caching | buffer pool of mutable pages; hot pages stay hot under updates | block cache of immutable blocks; trivial validity, churned by compaction |
| Write amplification | ≈ 6–80× (page/row, shared per checkpoint) | ≈ 5× tiered, ≈ 18× leveled |
| Read amplification | ≈ 1 page (point), 1 run (range) | ≈ 1.06 blocks (point), 7–36 runs (range) |
| Space | ≈ 1.4× (70% fill) + dead tuples; moderate compression | ≈ 1.1× leveled, ≈ 2× tiered; 3–5× block compression |
| Concurrency | latches per page, crabbing, right-links; MVCC version chains | immutable files, lock-free skip list, snapshot = sequence number |
| Fragmentation | half-empty and out-of-order pages over time; REINDEX | no page fragmentation; stale versions until compaction |
| Durability path | WAL + checkpoint of dirty pages | WAL + flush; files complete or absent |
What the B+ tree is actually good at
Reads with locality. Once the upper levels are cached a point read is one page, a range read is a sequential leaf walk, and ORDER BY, MIN, MAX and prefix predicates all fall out of the sorted leaves. Hot-row updates are cheap in aggregate: many changes to the same page share one write at checkpoint. Latency is predictable — there is no background process that can decide to consume the disk. The ecosystem built around it — MVCC in the heap, covering indexes, index-only scans, clustered primary keys in InnoDB Internals: Clustered Index, Buffer Pool, Redo, Undo, Locks — assumes in-place pages.
Its weak spot is random small writes across a working set larger than RAM: each one is a page read to find the leaf and a page write to persist it, and the tree fragments as it goes. Sequential inserts (auto-increment keys, timestamps) sidestep most of that, which is why "use a sequential primary key" is standard InnoDB advice.
What the LSM tree is actually good at
Ingest. Writes are a sequential append and a memory insert, throughput is bounded by disk bandwidth rather than IOPS, and flushes and compactions are large sequential operations that SSDs and HDDs both like. Sorted immutable blocks compress far better than pages, so the same data is smaller — MyRocks's headline result. Immutability makes replication, backup and snapshotting a matter of copying files, and makes concurrency almost free. Negative lookups are nearly free thanks to bloom filters, and time-bucketed data can be expired by deleting whole files.
Its weak spots are range scans across many runs, the tombstone lifecycle, and compaction as an operational concern: it competes with foreground I/O, it can fall behind and stall writes, and its tuning (level ratio, bloom bits, thread count, rate limits) is a discipline of its own. Latency is less predictable than a B+ tree's because background work is always in flight.
Real engines and hybrids
B+ tree side: PostgreSQL (heap tables plus B+ tree indexes, see PostgreSQL Internals: Heap, Tuples, Shared Buffers, WAL, VACUUM), MySQL/InnoDB (clustered B+ tree on the primary key, see InnoDB Internals: Clustered Index, Buffer Pool, Redo, Undo, Locks), SQLite (one B+ tree per table and index in a single file), Oracle, SQL Server, and MongoDB's WiredTiger in its default mode. LSM side: RocksDB and LevelDB as embedded engines, Cassandra and ScyllaDB, HBase, and the storage layers of TiKV, CockroachDB (Pebble) and YugabyteDB (DocDB on RocksDB).
Hybrids show that the choice is per workload, not per company: MyRocks replaces InnoDB with RocksDB under the same MySQL SQL layer, chosen at Meta for space and write efficiency on user-data shards while InnoDB stays where range scans matter; WiredTiger implements both a B+ tree and an LSM layout behind one API; Bε-trees (TokuDB, PerconaFT) buffer writes inside B+ tree nodes to bring write amplification down without giving up one sorted structure. The Physical Layouts Compared: Heap + Secondary Index vs Clustered Index lesson puts the two B+ tree layouts — heap plus index versus clustered — side by side in the same spirit.
Decision list
Neither engine is a default. Read the workload first, then the list.
- Choose a B+ tree engine when reads dominate and have locality; updates hit hot rows; range scans, sorted access and
ORDER BYare common; latency must be predictable; you want the relational ecosystem (MVCC, covering indexes, constraints) as it exists today. - Choose an LSM engine when writes dominate and keys are not sequential; write bandwidth, SSD endurance or disk space is the constraint; reads are mostly point lookups of recent data or negative lookups; data expires by time; replication and backups by file copy matter; you can operate compaction.
- Choose a hybrid when one system carries both shapes — MyRocks-style LSM under SQL for space-bound tables, B+ tree tables for report queries — and accept that each table still lives on one side of the triangle.
- Re-check the decision when the mix changes: an OLTP table that becomes an append-only audit log, or an event stream that starts serving dashboards, has changed engine class even if it kept its name.
Key points
- B+ tree: update in place, one sorted structure, page splits, latches, buffer pool. LSM: append, sorted runs, immutable files, bloom filters, compaction.
- Point reads are roughly equal in steady state; range scans favour the B+ tree; random-key ingest favours the LSM by an order of magnitude.
- Write amplification is page-granular for B+ trees and compaction-driven for LSMs; space favours leveled LSM with compression; predictability favours the B+ tree.
- Compaction is the LSM's operational cost; fragmentation and bloat are the B+ tree's.
- PostgreSQL, InnoDB, SQLite are B+ trees; RocksDB, Cassandra, HBase are LSMs; MyRocks and WiredTiger show the choice is per workload.
- There is no universally better engine: choose by workload, and re-check when the workload changes.
B+ tree vs LSM
| dimension | B+ tree (PostgreSQL, InnoDB, SQLite) | LSM tree (RocksDB, Cassandra, HBase) |
|---|---|---|
| page reads per point read | fits3 (root + branch cached) → ≈ 1 disk read | acceptablememtable + 5–7 bloom checks → ≈ 1.06 block reads |
| writes per update | fitsWAL record + one 8 KB page later, shared with neighbours | acceptableWAL append + memtable; ~18× rewritten by leveled compaction |
| compaction / split overhead | fitsoccasional page split, local and bounded | acceptablebackground compaction consuming I/O the reads want |
| cache friendliness | fitshot pages stay pinned; updates keep them in place | acceptableimmutable blocks cache well, but compaction rewrites them → cache churn |
| range scans | fitsrare here; linked leaves anyway | acceptablerare here; merge across runs |
| space | fits~70% fill + dead tuples | fits~1.1× leveled |
When to use — and when not
- A B+ tree engine fits read-heavy, hot-update, range-scanning, latency-sensitive workloads — the classic relational profile.
- An LSM engine fits ingest-heavy, space-constrained, point-read, time-expiring workloads — the classic event and wide-column profile.
- A B+ tree does not fit sustained random-key ingest larger than RAM.
- An LSM does not fit range-scan-heavy analytics over live data or workloads that cannot absorb compaction bursts.
- Neither fits a workload nobody has measured; the comparison is only as good as the mix you feed it.
Failure modes
- Choosing by benchmark headline and meeting the other engine's weak spot in production.
- Migrating an OLTP table to an LSM store and watching report queries merge dozens of runs.
- Running an append-only event table on a B+ tree with random UUID keys and saturating the disk with page writes.
- Treating a hybrid as "best of both" instead of "one side per table".
Where you meet this
Back up to the practical layer, and across to the rest of Engineer Atlas.
- DSAB+ tree → In-place sorted structure of pages
- DSAMerge sort → Append sorted runs, merge later
- Distributed SystemsImmutable logs and snapshots → Why replicated stores favour LSM files