LSM tree against B-tree

Write cost, read cost and compaction for the two storage engines under most databases.

On the roadmap:Advanced · step 3: Storage engines

Intermediateabout 15 to 20 min6 experiments

Experiments

New here? A few short steps show what happens, one at a time.

Settings

How the LSM tree merges

Each level holds one sorted file, ten times larger than the one above. A full level is merged into the next one, which rewrites it. Reads are cheap, writes cost more.

Entries stored1 billion

Entries held in memory before saving1 million

Size ratio between levels10

Bloom filter bits per key10

Bytes per entry100

B-tree page size

LSM write amplification

16x

B-tree write amplification

42x

Sorted files to search

Disk reads for a lookup

1.01

At 1 billion entries a leveled LSM tree writes each entry about 16x over its life, against 42x for a B-tree, and keeps 2 sorted files to search. With 10 bits per key in Bloom filters a lookup reads about 1.01 files from disk.

The same data, three structures

Structure	Bytes written per byte stored	Files or levels to search	Disk reads, key present	Disk reads, key absent	Space used
LSM, leveled	16x	2	1.01	0.02	1.10x
LSM, tiered	4.0x	1	1.00	0.01	5.50x
B-tree	42x	6	1.00	1.00	1.43x

Space used for the tiered LSM is the typical worst case when data is overwritten often. Numbers are estimates from a simulation of the merges, with random keys and no deletes, to show the shape of the trade-off.

In plain words

A B-tree stores data in sorted pages and updates them in place, so one small write rewrites a whole page. A log-structured merge tree (LSM) collects writes in memory, saves them as sorted files, and merges files in the background. It writes less on every insert, and pays for it with merging and with more places to look when reading.

Why it matters

Most modern databases are built on one of the two. The B-tree behind PostgreSQL and MySQL, and the LSM behind Cassandra, RocksDB and many others, make opposite trade-offs between write cost, read cost and space. Knowing which sits under a database tells you what it is good at, and what its background work will cost you.

How real systems do it

The simulation is a simplified model. Here is what production systems add or do.

RocksDB (from Facebook, built on Google's LevelDB), Cassandra, HBase, ScyllaDB and the storage engines of many other databases are LSM trees. PostgreSQL, MySQL's InnoDB, SQLite and most older relational databases use B-trees.
RocksDB offers both leveled and tiered (which it calls universal) compaction, and recommends Bloom filters. Cassandra's default for a table is size-tiered compaction, with leveled available for read-heavy tables.
An LSM tree writes sequentially, which is fast on both SSDs and spinning disks, and puts less wear on flash by writing less. The background compaction competes with foreground traffic for disk and can cause latency spikes.
Write amplification is the ratio of bytes written to storage to bytes the application wrote. A high ratio costs throughput and wears out flash, so engines tune it against read speed and space.