Archivestorage
B-Trees vs LSM Trees
One updates in place, the other appends. The choice shapes write amplification, read latency, and space usage.
- Published
- Reading time
- 1 min read
B-trees keep sorted pages and update them in place. LSM trees append to sorted files and merge later. Both give ordered access; they distribute the cost differently.
| B-tree | LSM | |
|---|---|---|
| Write path | random page updates, WAL | sequential appends |
| Read path | O(log n) page lookups | check multiple levels |
| Space | fragmentation, free pages | obsolete versions until compaction |
| Write amplification | moderate | high but sequential |
| Best for | read-heavy, OLTP | write-heavy, ingest |
The nuance
Modern engines blur the line: B-trees use WAL and buffer pools; LSM engines add bloom filters, partitioned indexes, and tiered compaction. On NVMe, random writes are less catastrophic than they were on spinning disks, which weakens the classic LSM advantage.
What to measure
Write amplification (bytes written per logical byte), p99 read latency after compaction spikes, and space amplification. Those three numbers decide more than the data structure label.
Takeaway: pick by workload shape and measure the three amplifications. "LSM is faster" is only true for a specific mix.