Course contentsShow
← Computer Science
Lesson 1740 of 2,87239. NoSQL and Modern DatabasesFree lesson

Physical Storage: SSTables and Log-Structured Merge Trees

Explore how column-family databases use SSTables and LSM trees for efficient write-heavy workloads and compaction.

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:

  1. MemTable (Memory): New writes go into an in-memory sorted structure first—fast!
  2. 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.
  3. 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.