Concept · Storage & databases
B-trees vs LSM-trees
Update in place or append and compact: the two storage-engine designs and their trade-offs.
Most databases store data with one of two engine designs. Knowing which one a database uses predicts how it behaves under reads, writes and background load.
B-trees: update in place
Used by PostgreSQL, MySQL (InnoDB), SQL Server and Oracle. Data lives in fixed-size pages (often 8 or 16 KB) arranged as a balanced tree. A lookup walks from the root to a leaf, usually three or four page reads, most of them cached in memory. A write finds the right page and modifies it, after first recording the change in the write-ahead log so a crash can be recovered.
- Predictable reads, and range scans walk leaf pages in key order.
- Writes are random I/O to wherever the page lives; a full page splits in two.
- Updates may leave dead space (PostgreSQL's vacuum reclaims it).
LSM-trees: append and compact
Used by Cassandra, ScyllaDB, RocksDB, LevelDB, HBase and the storage layer of many distributed databases.
- A write appends to the log and inserts into an in-memory sorted table (the memtable). That's the whole write cost.
- A full memtable is flushed to disk as an immutable sorted file (an SSTable).
- Compaction merges SSTables in the background, keeping the newest value of each key and dropping deleted ones (deletes are written as tombstones).
A read checks the memtable, then SSTables from newest to oldest. A Bloom filter per SSTable skips files that can't contain the key.
Trade-offs
| B-tree | LSM-tree | |
|---|---|---|
| Write throughput | Good | Very high (sequential I/O) |
| Point reads | One tree walk | Several files, made cheap by Bloom filters and caches |
| Write amplification | Page rewrites + WAL | Data rewritten by each compaction level |
| Space | Partly empty pages | Dense files; overwritten data lingers until compaction |
| Background work | Vacuum, page splits | Compaction, which competes with foreground I/O |
Rule of thumb: B-trees for general-purpose, read-heavy transactional workloads; LSM-trees for write-heavy data such as events, metrics, messages and logs. The SQL roadmap's indexes lesson shows B-tree lookups step by step.