Physical Storage: SSTables and Log-Structured Merge Trees
What you'll learn: How column-family databases achieve blazing-fast writes using SSTables and LSM trees, and why they need periodic compaction.
The Write Performance Problem
Traditional B-Tree indexes require random disk writes that hunt for the right spot to insert data—slow and expensive. Column-family databases like Cassandra and HBase flip this model: they use Log-Structured Merge (LSM) trees to turn random writes into sequential writes.
How LSM Trees Work
Think of LSM trees like a busy restaurant kitchen with multiple prep stations:
- MemTable (Memory): New writes go into an in-memory sorted structure first—fast!
- SSTables (Disk): When the MemTable fills up, it's flushed to disk as an immutable Sorted String Table (SSTable)—a sorted file of key-value pairs.
- Multiple Levels: Over time, you accumulate many SSTables at different "levels."
SSTables: Immutable and Sorted
An SSTable is a read-only file containing sorted column data. Because it's immutable, writes never modify it—they just create new SSTables. This enables:
- Sequential disk writes (much faster than random)
- Easy replication (copy whole files)
- Simple crash recovery
Compaction: Housekeeping Required
The downside? Reads must check multiple SSTables to find the latest value for a key. Compaction solves this by periodically merging and sorting multiple SSTables into fewer, larger ones—discarding old/deleted values. It's like organizing messy sticky notes into a single clean notebook.
This background process balances write speed with read efficiency and reclaims space.
Key Takeaway:
LSM trees use in-memory MemTables and immutable disk-based SSTables to optimize write-heavy workloads, trading read complexity for exceptional write throughput—compaction keeps storage efficient over time.