Module 07 · Databases · Lesson 5 of 13
LSM trees
The write-optimised engine behind Cassandra, RocksDB and most time-series stores. Memtables, sorted string tables, compaction, Bloom filters for reads, and the read and space amplification traded for sequential writes.
The video walkthrough is part of Pro.
See what Pro includesWhy it matters
B+ trees update pages in place, which makes random writes expensive. For workloads that are mostly writes (events, metrics, messages, logs) a different bet pays off: never update in place, only append, and tidy up later. That bet is the log-structured merge tree, and it is why Cassandra ingests millions of writes a second, why RocksDB sits under so many databases, and why "write-heavy" in an interview should trigger this lesson.
The idea
An LSM tree turns random writes into sequential ones. Writes go to an in-memory sorted structure; when it fills, it is flushed to disk as an immutable sorted file; background compaction merges files to keep reads bounded. Nothing on disk is ever modified, only written and eventually deleted.
- 1
Write to the log and the memtable
Each write is appended to a write-ahead log for durability and inserted into the memtable, an in-memory sorted structure (a skip list or balanced tree). The write is acknowledged now; it never touched a disk page. - 2
Flush to an SSTable
When the memtable reaches a size threshold (tens of megabytes), it is written to disk sequentially as a sorted string table: sorted key-value pairs plus a sparse index and a Bloom filter. The memtable is replaced and the log segment discarded. - 3
Read by checking newest to oldest
A read checks the memtable, then SSTables from newest to oldest, returning the first match. Bloom filters let it skip files that definitely do not contain the key; the sparse index finds the block within a file that might. - 4
Compact in the background
Compaction merges several SSTables into fewer, larger ones, dropping overwritten versions and tombstoned deletes. It bounds how many files a read must check and reclaims space.
Compaction strategies
Size-tiered compaction merges files of similar size into bigger ones: cheapest writes, but a key may exist in many files and space can briefly double during a merge. Leveled compaction keeps each level as non-overlapping sorted runs, each level about ten times the previous: reads check at most one file per level and space overhead is small, but writes are rewritten more often. Cassandra defaults to size-tiered and offers leveled; RocksDB defaults to leveled. Time-series stores use time-window compaction so old data is never rewritten and expires by dropping whole files.
The three amplifications
| B+ tree | LSM tree | |
|---|---|---|
| Write amplification | Every write dirties pages in each index; random writes | Sequential appends, but each byte is rewritten once per level during compaction (often 10 to 30 times over its life) |
| Read amplification | One descent per index; predictable | Several files may be checked per read; Bloom filters and compaction keep it bounded but variable |
| Space amplification | Pages around 70 percent full after random inserts | Old versions and tombstones persist until compaction; leveled keeps it near 1.1×, size-tiered can reach 2× |
| Best for | Read-heavy, range scans, in-place updates | Write-heavy ingest, append-mostly data, large datasets on SSD |
Operational realities
Compaction competes with foreground traffic for disk and CPU, and a system that cannot keep up accumulates files and sees read latency climb; monitoring pending compactions is as important as monitoring queue depth. Deletes are tombstones that take space until compacted past every older version, so delete-heavy workloads can grow instead of shrink. Range scans must merge across files and are slower than a B+ tree leaf walk. Bloom filters cost memory proportional to key count and are what make point reads acceptable at all.