Why LSM Trees? Write-Optimized Storage

A Log-Structured Merge tree (LSM tree) is the storage engine behind LevelDB, RocksDB, Cassandra, ScyllaDB, HBase, BadgerDB, Bigtable, and many time-series databases. It's optimized for write-heavy workloads — the opposite trade-off from a B-tree.

The Core Problem

A B-tree mutates pages in place. Every insert eventually does a random write to disk: find the leaf page, modify it, fsync. With billions of small writes, those random IOPS become the bottleneck. Modern SSDs handle ~100K random writes/sec; HDDs barely break 200/sec.

The LSM Insight

What if every write is sequential and append-only, and we sort it out later in the background? That's an LSM tree:

1. Writes go to an in-memory sorted structure (the memtable).
2. When the memtable fills, it's flushed to disk as a sorted,
   immutable file called an SSTable.
3. Background compaction merges SSTables to keep read paths short.

The write path never touches existing files. New data is appended; old data is rewritten in bulk during compaction. Sequential I/O is 100-1000x faster than random I/O on every storage medium.

Trade-offs vs B-tree

Where LSM Wins

• High write throughput: append-only beats in-place mutation.
• SSD endurance: sequential writes spread wear evenly.
• Compression: SSTable blocks compress beautifully (~3-5x).
• Snapshots: immutable files make consistent snapshots free.

Where B-tree Wins

• Point reads: a B-tree lookup is O(log N) pages; an LSM lookup may touch many SSTables.
• Predictable latency: B-trees don't have compaction pauses.
• Space efficiency: no obsolete versions waiting to be compacted.

LSM trees are not "better" than B-trees — they're a different point on the read/write/space trade-off triangle.

What You'll Build

By the end of this course you will have built a working LSM tree storage engine:

• Memtable (skip list or sorted dict)
• Write-ahead log with crash recovery
• SSTable file format with block index and bloom filter
• Flush from memtable to SSTable
• Size-tiered and leveled compaction
• Range queries via k-way merge iterators
• Snapshot reads via sequence numbers
• Tombstones for deletes