We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
This idea carries a full system design question on its own. Each walks through the full answer.
System Design Masterclass · Database Types Storage
Free preview: the first 2 parts of this 8-part lesson.
Already bought the course? Sign in to read the whole lesson.
this lesson is part of
System Design Masterclass
Unlock this lesson and the 751 other paid lessons
$25 once, by PayPal
See the System Design courseread the rest of this lesson in
System Design Masterclass
Unlock this lesson and the 751 other paid lessons
$25 once, by PayPal
See the System Design coursein Database Types Storage
This lesson is part of the full System Design Masterclass. Unlock it along with 769 other lessons for a one-time payment.
One-time payment by card or PayPal
Get Lifetime AccessOne-time payment: UPI, card or netbanking
Get Lifetime Access18 Foundation lessons are free, no payment needed. Try them now
It is easy and good
“It is really nice and good Please join the course”
B-trees are the default index structure in PostgreSQL, MySQL, Oracle, and Server. They've dominated database indexing for 50 years. For reads, they're excellent. O(log n) lookups with great cache locality.
But B-trees have a write problem.
When you insert a key into a B-tree, the database must find the correct leaf page, update it in place, and write the modified page back to disk. If the page is full, it splits, creating two pages, updating the parent pointer, and potentially cascading splits up the tree. Each of these operations is a random write to a different location on disk.
Random writes are the slowest operation on any storage device. An SSD handles maybe 50,000-100,000 random writes per second. A spinning HDD handles about 100-200. For a database ingesting millions of writes per second, think Cassandra handling IoT sensor data, or RocksDB as the storage engine for streaming platforms. B-trees can't keep up.
LSM trees (Log-Structured Merge-trees) flip the approach entirely. Instead of updating data in place, they buffer writes in memory and flush them to disk as large, sequential batches. Sequential writes are 100x faster than random writes on SSDs and 1000x faster on HDDs.
This single design decision, sequential writes instead of random writes, is why LSM trees power Cassandra, RocksDB, LevelDB, HBase, CockroachDB, ScyllaDB, InfluxDB, and virtually every database designed for high write .
An LSM tree has two main components: an in-memory buffer and on-disk sorted files.
1. Memtable (in-memory)
All writes go to an in-memory sorted data structure, typically a red-black tree or skip list. This is the memtable. Writes are fast because they're pure memory operations. The memtable also serves recent reads, if the key you're looking for was recently written, it's in memory.
A Write-Ahead Log (WAL) is written to disk for every write, ensuring durability. If the process crashes, the memtable can be rebuilt from the WAL.
2. SSTables (on-disk)
When the memtable reaches a size threshold (typically 64-256 MB), it's flushed to disk as an SSTable (Sorted String Table), an immutable, sorted file of key-value pairs. Because the memtable is already sorted, the flush is a single sequential write.
Over time, you accumulate many SSTables on disk. Each new flush creates a new file.
3. Compaction
With many SSTables, reads get slower, the database might have to check multiple files to find a key. Compaction is a background process that merges multiple SSTables into fewer, larger, sorted files, similar to merge sort. Old files are deleted after a successful merge.
Compaction is the most critical and complex part of an LSM tree. It directly affects read performance, write amplification, and space amplification.