Overview
B-Trees and LSM Trees are the two dominant on-disk index structures used by databases, and they diverge on how they handle writes. A B-Tree performs in-place updates on a balanced page structure to keep reads fast, while an LSM Tree buffers writes in memory and reconciles them later through background compaction, trading read simplicity for write throughput.
Comparison Diagram
Comparison Table
| Aspect | B-Tree | LSM Tree |
|---|---|---|
| Write path | Traverses the tree to locate the target page and updates it in place, splitting nodes as needed | Appends the entry to an in-memory memtable plus a write-ahead log; no seek to the record’s final location |
| Read path | Single root-to-leaf traversal, O(log n) page reads from one location | Checks the memtable then potentially multiple SSTables across levels, often aided by bloom filters |
| Update/Delete handling | Overwrites the existing value directly at its page | Writes a new version or a tombstone; the old entry is only removed later during compaction |
| On-disk structure | One mutable, balanced tree of fixed-size pages, always sorted | Immutable sorted SSTable files organized into levels of increasing size |
| Background maintenance | Node splits and merges happen incrementally as part of each write | Periodic compaction merges SSTables across levels and drops stale versions |
| Write amplification | Low to moderate; occasional page rewrites and splits | Higher; the same record can be rewritten multiple times as it moves through levels |
| Read amplification & space reclaim | Minimal read amplification; deleted space is reclaimed immediately | Higher read amplification from scanning multiple levels; space reclaimed only after compaction |
| Range scans | Efficient via sorted leaf pages linked in order | Efficient within a level but requires merging sorted runs across levels |
Key Differences
- A B-Tree updates data in place, while an LSM Tree defers changes through append-only writes to a memtable
- LSM Trees gain higher write throughput by avoiding random disk seeks, at the cost of ongoing compaction
- B-Trees give more predictable read latency since each key lives in exactly one place
- LSM read and space overhead comes from having to consult multiple SSTable levels
- Deletes in an LSM Tree are recorded as tombstones rather than removed immediately
When to Use Each
B-Tree
- Read-heavy OLTP workloads: A single predictable traversal path keeps lookup latency low and consistent when reads dominate.
- Sorted range queries: Linked leaf pages let the tree scan ordered ranges without merging multiple data sources.
- Frequent small in-place updates: Overwriting a value directly avoids the version bookkeeping and later cleanup that log-structured designs require.
LSM Tree
- Write-heavy ingestion: Buffering writes in memory and flushing sequentially avoids the random I/O cost that dominates B-Tree writes.
- SSD-optimized storage engines: Sequential SSTable writes reduce write amplification on flash compared to scattered in-place page updates.
- Systems that can tolerate compaction pauses: Workloads like time-series or log storage can trade occasional compaction overhead for sustained write speed, as in Cassandra or RocksDB.