4.4 Comparing B-Trees and LSM-Trees
LSM vs B-tree
LSM sustains higher write throughput and compresses better, but compaction competes with foreground traffic — and at high write rates compaction can fall behind, which is the failure mode to watch.
Rule of thumb: LSM-trees are better for write-heavy applications; B-trees are faster for reads.
But benchmarks are often sensitive to workload details — you need to test with YOUR workload. And it's not a strict either/or: storage engines sometimes blend both (e.g. multiple B-trees merged LSM-style).
4.1 Read performance
| B-tree | LSM | |
|---|---|---|
| Point lookup | Read one page per level; few levels ⇒ fast and predictable | Often must check several SSTables at different compaction stages; Bloom filters reduce the disk I/O |
| Range query | Simple and fast — uses the sorted tree directly | Can use SSTable sorting, but must scan all segments in parallel and combine results. Bloom filters DON'T help (you'd need the hash of every possible key in the range — impractical) ⇒ range queries are more expensive than point queries in LSM |
LSM write-throughput hazard: high write throughput can cause latency spikes if the memtable fills up — data can't be written to disk fast enough, perhaps because compaction can't keep up with incoming writes. Many engines including RocksDB apply backpressure: they suspend all reads and writes until the memtable has been written out.
Modern SSDs, especially NVMe (PCIe bus rather than SATA), perform many independent read requests in parallel. Both structures can deliver high read throughput, but the engine must be carefully designed to exploit that parallelism.
4.2 Sequential vs random writes
| B-tree | LSM |
|---|---|
| Keys are scattered over the key space, so the pages are scattered too. | Whole segment files are written at a time. |
▓ · · ▓ · ▓ · · · ▓ · · ▓ · · — many small random writes | ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ — fewer, much larger sequential writes |
Disks have higher sequential write throughput than random, so a log-structured engine can generally handle higher write throughput on the same hardware. The difference is particularly big on spinning disks; on SSDs it's smaller but still noticeable.
Why SSDs still prefer sequential writes (this is the sub-section people most often skip and most often need):
- Flash can be read or written one page at a time (typically 4 KiB) but erased only one block at a time (typically 512 KiB).
- Before erasing a block, the controller must move pages containing valid data into other blocks — garbage collection (GC).
- Sequential workload: large chunks written at once → a whole 512 KiB block likely belongs to a single file → when deleted, the whole block can be erased with no GC.
- Random workload: a block more likely contains a mixture of valid and invalid pages, so GC must do more work before erasing.
- Two consequences: GC's write bandwidth is not available to the application, and the extra writes wear the flash — random writes wear out the drive faster than sequential writes.
4.3 Write amplification
Write amplification = (total bytes written to disk in a workload) ÷ (bytes you'd write with a plain append-only log and no index). (Sometimes defined in I/O operations rather than bytes.)
Where the extra writes come from:
| Engine | Writes per logical write |
|---|---|
| LSM | (1) the WAL for durability, (2) the memtable flush to disk, (3) again every time the pair is part of a compaction |
| B-tree | (1) the WAL, (2) the tree page itself — plus sometimes writing out an entire page even if only a few bytes changed, to guarantee correct recovery after a crash or power failure |
Optimization for LSM: if values are much larger than keys, store values separately from keys and compact only the SSTables containing keys + value references (this is WiscKey-style key-value separation, used by RocksDB's BlobDB and TiKV's Titan).
Why it matters: in write-heavy applications the bottleneck may be the rate at which the database can write to disk. The higher the write amplification, the fewer writes/second within the available disk bandwidth. It also determines SSD wear.
Which is better depends on: key/value lengths, and how often you overwrite existing keys vs insert new ones. For typical workloads, LSM-trees tend to have LOWER write amplification because they don't have to write entire pages and can compress chunks of the SSTable.
⚠️ Benchmarking warning: run the experiment long enough that write amplification becomes visible. When writing to an empty LSM-tree there are no compactions yet, so all disk bandwidth is available for new writes. As the database grows, new writes must share bandwidth with compaction. Short benchmarks systematically flatter LSM engines.
4.4 Disk space usage
| B-tree | LSM | |
|---|---|---|
| Fragmentation | Yes. Deleting many keys leaves unused pages in the middle of the file; they can be reused but can't easily be returned to the OS → needs a background process to move pages around, e.g. PostgreSQL's vacuum | Less of a problem — compaction periodically rewrites the files anyway, and SSTables have no pages with unused space |
| Compression | — | Blocks of key-value pairs compress better in SSTables, often resulting in smaller files than B-trees |
| Space overhead | — | Overwritten/deleted keys consume space until removed by compaction — low with leveled compaction; size-tiered uses more, especially temporarily during compaction |
| Verified deletion | — | A deleted record may still exist in higher levels until the tombstone has propagated through all compaction levels, which might take a long time — a genuine problem for data-protection compliance. Specialist designs can propagate deletions faster |
| Snapshots | Harder — pages are overwritten | Easy: write out the memtable, record which segment files existed at that time. As long as you don't delete those files, you don't need to copy anything |