LSM Trees

Never update a file in place: buffer writes in memory, flush them as sorted immutable files, and merge those files in the background. Reads pay for it by checking several places — and Bloom filters cut that cost.

Write: O(1) amortised

Read: O(levels)

RocksDB · Cassandra · LevelDB

Workload

Animation Speed: 1100ms

Step 1 of 0

Click Play to begin.

LSM Tree vs B-Tree

	LSM tree	B-tree
Write	memtable + sequential flush	random in-place page write
Read	memtable, then each level	one root-to-leaf path
Delete	tombstone, removed later	remove from the leaf
Extra work	background compaction	page splits
Best for	write-heavy ingest	read-heavy, range scans

Real engines keep many levels, each about ten times larger than the one above, and split each level into many small SSTables so compaction can work on a slice at a time.

Knowledge Check

Question 1 of 3

Why are writes cheap in an LSM tree?

DSAverse

LSM Trees

LSM Tree vs B-Tree

Knowledge Check

See also

LSM Trees

LSM Tree vs B-Tree

Knowledge Check

See also