LSM Trees and SSTables
LSM trees turn random writes into sequential ones: write to a log and an in-memory table, flush immutable sorted files, and compact in the background. Follow writes, a read and a compaction, then weigh write, read and space amplification.
🎯 What you'll learn
- Why optimize for writes
- Memtable + WAL, flushing to immutable SSTables
- Reads across levels with Bloom filters
- Compaction and the amplification trade-offs; LSM vs B-tree
📚 Before you start
1A Different Trade-off: Optimize Writes, Not Reads
02-b_tree/ covered the structure behind most relational-database indexes — a structure that updates itself in place on every write, which means every insert/update potentially touches random locations on disk. A Log-Structured Merge-tree (LSM tree) makes the opposite bet: never modify data in place, only ever append — turning random writes into sequential ones — and pay the cost back later, on reads and in the background. This is the structure behind write-heavy NoSQL and wide-column stores: Cassandra, RocksDB, LevelDB, and (as a storage engine option) InfluxDB and ScyllaDB.
2The Memtable: Writes Land in Memory First
WRITE path:
client write -> append to an in-memory sorted structure (the "memtable")
-> (also appended to an on-disk write-ahead log, for crash safety)Every write — insert, update, even delete (recorded as a special "tombstone" marker, not an in-place removal) — is first appended to an in-memory memtable, typically a balanced tree or skip list kept sorted by key. Because this is a pure append to memory, writes are extremely fast: no disk seek, no in-place page rewrite, no B-tree rebalancing.
3Flushing to SSTables: Immutable, Sorted Files on Disk
memtable fills up ------> flushed to disk as a new SSTable (Sorted String Table)
(memtable is now empty again, ready for new writes)
Disk ends up with MANY SSTables, from successive flushes:
SSTable_1 (oldest) SSTable_2 SSTable_3 SSTable_4 (newest)Once the memtable reaches a size threshold, it's flushed to disk as an SSTable — a file holding sorted key-value pairs, written once and never modified again (hence "immutable"). A fresh, empty memtable takes over for new writes. Over time this produces many SSTable files on disk, each representing a batch of writes from some point in the past.
4Reads: Check the Memtable, Then Search SSTables (Newest First)
A read for a given key has to check the memtable first (the newest data, not yet flushed), then fall back to searching SSTables on disk, from newest to oldest, until it finds the key — since the same key can appear in multiple SSTables (a later write superseding an earlier one), the first match found (searching newest-first) is the current value. This is fundamentally more work than a B-tree's single-structure descent, and each SSTable's own internal index (often itself a small B-tree or a sparse index + Bloom filter) is what keeps that per-file search fast rather than a full file scan.
GET "user:42":
1. check memtable -> not found
2. check SSTable_4 (newest) -> not found
3. check SSTable_3 -> FOUND, return this value, stop
(an older value for "user:42" might still exist in SSTable_1 -- irrelevant, it's stale)5Compaction: Merging SSTables in the Background
Left unchecked, the number of SSTables would grow without bound, and every read would get slower as it had more files to check. A background process called compaction periodically merges multiple SSTables into fewer, larger ones — discarding superseded values (an old value hidden by a newer write to the same key) and physically removing tombstoned (deleted) keys once it's safe to do so. Compaction is what keeps read amplification bounded over the structure's lifetime; it's a continuous background cost, paid asynchronously, in exchange for the write path never having to do this work synchronously.
6Write Amplification vs. Read Amplification vs. Space Amplification
| Factor | B-tree | LSM tree |
|---|---|---|
| Write cost | In-place update: read-modify-write a page, possible node split — random I/O | Pure sequential append to memtable/log — cheap, but the same logical write gets re-written again later during compaction (this re-write is "write amplification") |
| Read cost | Single descent through one structure | Potentially check memtable + several SSTables until a match is found ("read amplification") — mitigated by Bloom filters and compaction |
| Space cost | Roughly proportional to live data | Stale/superseded values and tombstones linger until compaction reclaims them ("space amplification") |
Neither structure wins on all three axes simultaneously — this is a fundamental trade-off, not an implementation detail one engine got wrong. LSM trees deliberately shift cost away from the write path (fast, sequential) onto the read path and a background process (compaction), which is exactly backwards from a B-tree's in-place-update, single-structure-read design.
7When LSM Beats B-tree
Write-heavy workloads with high ingest rates (time-series data, event logs, metrics, IoT sensor streams) are where LSM trees shine — turning what would be constant random-I/O B-tree page rewrites into sequential appends is a large, measurable win at high write volume. Read-heavy or read-latency-sensitive workloads, or workloads needing strong range-query performance with minimal per-read overhead, tend to still favor B-trees — which is exactly why relational databases (PostgreSQL, MySQL's InnoDB) default to B-tree indexes, and why the systems that pick LSM trees (Cassandra, RocksDB) are typically built for ingest-heavy use cases from the start.
⚠️ Common Pitfalls
- Assuming LSM trees are "just generally faster" than B-trees — they trade write speed for read complexity; a read-heavy workload with modest write volume is usually worse off on an LSM-backed store.
- Forgetting that deletes are tombstones, not immediate removal — a deleted key's old value(s) physically remain on disk, taking up space and potentially slowing reads, until compaction actually removes them.
- Not accounting for compaction as a real, ongoing resource cost — compaction consumes CPU and I/O in the background; under-provisioning for it is a common cause of an LSM-backed store's performance degrading under sustained high write load.
- Expecting range queries to be as cheap as on a B-tree — a range scan on an LSM tree may need to merge results across the memtable and multiple SSTables in sorted order, more work than a single B-tree's linked-leaf traversal (
02-b_tree/section 4).
📋 Quick Reference
LSM tree: writes -> memtable (in-memory, sorted) -> flushed to immutable SSTables on disk
Read: check memtable, then SSTables newest-to-oldest, until a match is found
Compaction: background merge of SSTables -> bounds read amplification & reclaims space
Delete = tombstone marker, not in-place removal -- reclaimed later by compaction
B-tree: optimizes READS (single structure, in-place updates) -- relational DB default
LSM tree: optimizes WRITES (sequential append, deferred merge) -- Cassandra, RocksDB, LevelDB
Trade-off axes: write amplification vs read amplification vs space amplification
-- no structure wins all three; pick based on the workload's write:read ratio🧠 Key takeaways
- LSM trees buffer writes in a memtable (+ WAL) and flush immutable sorted SSTables: sequential I/O, high write throughput.
- Reads check memtable then SSTables newest-first; Bloom filters and indexes limit files touched.
- Compaction merges files and removes overwritten data and tombstones (tunable: leveled vs tiered).
- Choose LSM (RocksDB, Cassandra) for write-heavy workloads; B-trees for read-heavy, update-in-place patterns.
🎤 Interview Q&A
Q1How does an LSM tree handle writes?core▾
Writes are appended to a write-ahead log for durability and inserted into an in-memory sorted memtable. When full, the memtable is flushed to disk as an immutable sorted file (SSTable). Writes are sequential, which makes them very fast.
- What happens on crash? The memtable is rebuilt by replaying the WAL.
Q2How are reads served in an LSM tree?core▾
Check the memtable, then SSTables from newest to oldest. Bloom filters per SSTable skip files that definitely don't contain the key, and sparse indexes locate the block inside a file.
- Why are reads slower than B-trees? A key may need checks across several levels or files.
Q3What is compaction and why is it needed?senior▾
Background merging of SSTables to remove overwritten and deleted entries (tombstones) and reduce the number of files to read. Size-tiered compaction favours write throughput; leveled compaction favours reads and space at the cost of more write amplification.
- Risk of compaction? It competes with foreground I/O; falling behind increases read latency and disk usage.
Q4How are deletes handled?core▾
A delete writes a tombstone marker; the data is physically removed only during compaction once the tombstone is older than all copies. Too many tombstones slow reads (a known Cassandra issue).
- Why not delete immediately? SSTables are immutable.
Q5Explain read, write and space amplification.core▾
Write amplification: bytes written to disk per byte written by the app (compaction rewrites data). Read amplification: number of disk reads per query. Space amplification: disk used vs live data size. LSM designs and compaction strategies trade these against each other.
- Which is B-tree's main cost? Write amplification from rewriting whole pages for small updates.
🛠️ Practice exercises
Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.
✅ Check yourself
Answer the questions — feedback is instant.