B-Tree vs LSM-Tree
Compare B-tree and LSM-tree write, read and compaction costs through two visual models, then choose what to measure for your workload.
A B-tree maintains ordered pages as it writes; an LSM-tree first buffers writes and later merges sorted runs. That shifts some work between foreground writes, background compaction and reads. Compare real latency, throughput and space under your engine's configuration before choosing.
A B-tree is a filing cabinet kept in order as letters arrive. An LSM-tree starts with an inbox tray and sorts batches later. Filing now and sorting later both take work; which feels faster depends on how often you add, search and reorganize letters.
When writes or reads slow down, the storage engine is one possible cause. B-trees and LSM-trees organize work differently: one maintains ordered pages as writes arrive, while the other buffers updates and later compacts sorted runs. The diagrams below show those mechanisms. They do not predict a product’s latency from its data-structure name alone.
B-TREE · POSTGRES, MYSQL, SQLITE
LSM-TREE · CASSANDRA, ROCKSDB, SCYLLADB
Everything below is the detail behind that trade — including the two cases where the rule of thumb is wrong.
The first interactive figure sketches two to four B-tree index levels and two to five LSM levels as the example row count changes. Those level counts are drawing choices, not a prediction for any product or data size. The second figure keeps repeated updates to one key visible before compaction; it does not estimate retained versions or storage bytes after cleanup. Neither figure uses measured page I/O, timing, write amplification or a benchmark of PostgreSQL, RocksDB or Cassandra. Actual tree height, cache hits, Bloom-filter use, compaction policy and durability settings change the costs. The mechanisms follow PostgreSQL’s B-tree documentation and RocksDB’s storage-engine overview. Use the controls to inspect where work can occur, then measure your own engine and workload.
Static write-path example at 1M rows: this sketch follows 4 B-tree index levels; the LSM buffers and logs the update before later flushes and compaction. These are drawing choices, not measured disk reads. JavaScript controls are needed to compare the read path or change the illustrated row count.
Where the cost actually lands#
A write ● into a B-tree finds the page where the key belongs and updates the ordered structure; a full page can split and affect its parent. The split visualizer walks through that structural case key by key. A database may buffer dirty pages and log a change before writing data pages, so the drawing is not a claim that every request performs a synchronous page read and write.
In a RocksDB-like LSM design, a write ● enters an in-memory table and, when configured for durability, a write-ahead log. Later flushes and compactions merge sorted files. The foreground path avoids placing the update into its final on-disk sorted run immediately; it can still wait on durability or stall when background work falls behind.
A B-tree does not need an LSM’s merge of sorted runs, but that does not make a B-tree database free of maintenance. PostgreSQL writes buffered pages and removes obsolete row and index versions when they are safe to discard. Some index cleanup happens during inserts; vacuum also cleans indexes. PostgreSQL’s index-deletion documentation describes both. Neither vacuum nor LSM compaction means that ordinary reads were searching a broken index: both structures must remain searchable while maintenance is pending.
A read ▬ through a B-tree follows levels to a leaf, but tree height is not a universal three or four physical reads: cached pages may need no disk read, and some queries then fetch a table row. The query planner may choose a sequential scan instead. An LSM point lookup checks the memtable and the candidate sorted runs in the configured levels; key ranges and Bloom filters can rule out some files without reading their data. Positive lookups, false positives, range scans and compaction can change the result. This is why the diagrams explain a cost path rather than promise a latency number.
Static example: after 4 updates to one key, v4 is the newest value in this sketch. The LSM drawing keeps those versions visible before compaction; the B-tree drawing shows one indexed key location. JavaScript controls are needed to change the update count. This does not measure storage bytes or predict retained versions after cleanup.
Fewer rewrites can leave more files to search. More aggressive compaction can shorten reads but increase background writes—and may stall foreground writes when it falls behind.
Which compaction, and what it costs#
A compaction policy chooses which sorted files to merge or discard, and when to do it. For example, with four similarly sized files waiting, a size-tiered policy may merge them as a batch, while a leveled policy rewrites files to keep key ranges from overlapping in later levels.
These are two useful patterns, not the complete set. Cassandra 5.0’s Unified Compaction Strategy (UCS) can combine tiered and leveled behaviour; its time-window strategy groups expiring time-series files by time. RocksDB offers universal (tiered) and FIFO styles alongside leveled compaction.
RocksDB’s FIFO policy can discard the oldest table files when their total size exceeds a configured limit; this is retention, not proof that their values are obsolete. Optional merging can also be enabled.
In Cassandra’s size-tiered strategy (STCS), the default trigger is four similarly sized SSTables. They merge into one larger sorted file. This can reduce repeated rewriting compared with more aggressive leveled policies, but versions of a row may remain in more files, making reads consider more runs. Obsolete data can wait for a suitable merge. The old and replacement files coexist while compaction runs, so temporary disk headroom matters. This is a trade-off, not a promise that a particular write or read is faster.
Leveled compaction organises files into levels with increasing size targets. In RocksDB’s leveled design, files within each level below level 0 have non-overlapping key ranges, so a point lookup has at most one candidate file in each of those levels. Level 0 is the exception: recently flushed files can overlap, leaving several candidates. Cache hits and filters can avoid data reads, so candidate files are not a count of physical I/O. Compaction pays for this organisation by rewriting data into lower levels. RocksDB’s dynamic-level sizing aims to keep about ninety per cent of the data in the last level; that depends on its configuration, rather than being a property of every LSM-tree.
The choice is not limited to two policy labels. Tiered grouping often does less rewriting but leaves more runs to search. Leveled grouping rewrites data more often in exchange for narrower candidate key ranges outside level 0. UCS can tune that balance, and time-window policies serve a different pattern of expiring data. Compare the read and scan mix, sustained writes, deletion patterns, disk headroom and compaction stalls under the actual engine configuration.
The delete that is a write#
Suppose a key still exists in an older immutable run. Removing it only from the memtable would let a later read find the old value again. An LSM can instead write a deletion marker, called a tombstone, that hides the older value. The logical delete takes effect before compaction can reclaim the obsolete bytes. RocksDB’s deletion explanation describes this problem in a local engine; it does not require replication.
Cassandra also has a replication problem to solve. A node that misses the delete can retain the old value and later bring it back during repair. Replicating the tombstone gives that node evidence that the value was deleted. Cassandra’s tombstone documentation explains this additional reason to retain the marker.
Cassandra’s gc_grace_seconds defaults to ten days. Passing that age makes a tombstone eligible for removal; it is not a promise that space returns on day ten. A suitable compaction must include the older data it hides, and repair-related settings can impose further conditions. Plan for retained markers and obsolete data, inspect compaction and repair progress, and do not treat the grace period alone as protection against replicas returning stale data.
Decide in one table#
| Situation | Take | Because |
|---|---|---|
| Write-heavy ingest, reads are mostly recent | Test an LSM | Buffered writes may help, if compaction keeps up and read costs fit. |
| Latency must be predictable at p99 | Test a B-tree | Its bounded tree depth can help; verify cache and tail latency. |
| Range scans over a sort key | Either | Both keep data sorted; the LSM merges runs while reading. |
| Many updates to the same rows | Compare both | Compaction and MVCC cleanup policies determine retained versions. |
| Random UUID primary key | Measure key effects | Key order can affect page locality and compaction work differently. |
- Situation
- Write-heavy ingest, reads are mostly recent
- Take
- Test an LSM
- Because
- Buffered writes may help, if compaction keeps up and read costs fit.
- Situation
- Latency must be predictable at p99
- Take
- Test a B-tree
- Because
- Its bounded tree depth can help; verify cache and tail latency.
- Situation
- Range scans over a sort key
- Take
- Either
- Because
- Both keep data sorted; the LSM merges runs while reading.
- Situation
- Many updates to the same rows
- Take
- Compare both
- Because
- Compaction and MVCC cleanup policies determine retained versions.
- Situation
- Random UUID primary key
- Take
- Measure key effects
- Because
- Key order can affect page locality and compaction work differently.
The bill nobody budgeted for#
Suppose a RocksDB-backed application ingests quickly during a short test, but writes slow once newly flushed files accumulate in level 0. RocksDB’s write-stall rules can delay writes at level0_slowdown_writes_trigger and stop them at level0_stop_writes_trigger. A backlog of immutable memtables or estimated pending compaction bytes can also stall writes. That background work now affects foreground latency, despite the initial in-memory write path. This is an illustrative failure path, not a measured incident; inspect sustained write latency and stall statistics after background work has been running.
A randomly ordered key can spread B-tree inserts across more leaf pages than a steadily increasing key. Whether that matters depends on the active key range, page occupancy, cache and write rate. It does not mean that every insert touches a different page or that the cache stops helping at one fixed size. Compare representative key distributions before treating the key format as the cause of a slowdown. If you are choosing an InnoDB primary key, the guide to clustered indexes explains where the row is stored and why secondary indexes carry that key.
IF YOU REMEMBER ONE THING
Trace where the work happens, then measure it under sustained load. Buffered writes can defer work, but compaction stalls can bring that cost back into request latency. B-tree page writes, splits and cleanup also have costs. The diagrams explain the mechanisms; they do not rank engines or predict a latency number.
The same trade asked of a whole workload rather than a single key is row storage against column storage, where what decides it stops being how often you write and starts being how much of each row you actually read.
Questions people also ask
5 QUESTIONSWhich one does Postgres use?
PostgreSQL uses B-trees for its default indexes. RocksDB is an LSM-based storage engine, and Cassandra, ScyllaDB and LevelDB also use LSM-style designs. This distinction describes one part of each system; query planning, caching, replication and configuration also affect observed behavior.
Is an LSM-tree always faster for writes?
No universal speed ranking follows from the data structure alone. Buffering and sequential writes can help ingest, but WAL durability, memtable limits, compaction stalls, cache behavior and the workload affect measured write latency and sustained throughput.
What is write amplification?
The ratio of physical storage bytes written to logical bytes the application asked to write, over a defined interval and accounting boundary. Page updates, WAL, flushes and compaction can all contribute; compare engines using the same workload and measurement boundary.
Do bloom filters make LSM reads as fast as B-tree reads?
Bloom filters can skip runs that definitely lack a queried key, especially for negative point lookups. They can have false positives and do not answer positive lookups or range scans by themselves. The benefit depends on filter configuration and the workload's lookup mix.
Can I switch from one to the other later?
Changing a primary storage engine usually requires a migration and revalidation of behavior, but a database may offer different index types or tuning choices without that change. Identify whether you are choosing an index, a table layout or an engine before planning the switch.