# B-trees vs LSM-trees

> Update in place or append and compact: the two storage-engine designs and their trade-offs.

Concept · Storage & databases · https://levelcode.org/concepts/b-tree-vs-lsm-tree

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](https://levelcode.org/concepts/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.

1. A write appends to the log and inserts into an in-memory sorted table (the **memtable**). That's the whole write cost.
2. A full memtable is flushed to disk as an immutable sorted file (an **SSTable**).
3. **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](https://levelcode.org/concepts/bloom-filters) 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.