A log-structured merge tree (LSM tree) is the storage design behind write-heavy databases such as Cassandra, RocksDB, LevelDB and ScyllaDB. Instead of updating data in place on disk like a B-tree, it collects writes in memory and writes them to disk in large sorted batches. Writes get much cheaper. Reads get somewhat more expensive, and a few clever tricks keep that cost under control.
The core trick: sequential instead of random writes#
Disk writes come in two flavours:
| Write type | What it means | Cost |
|---|---|---|
| Random | "Go to position 47,382 and update it" | On a spinning disk the head must physically move (milliseconds) |
| Sequential | "Append this to the end of the file" | The head barely moves. Far faster on HDDs and still faster on SSDs |
An LSM tree turns random writes into sequential ones. That is the whole idea.
The pieces#
An LSM tree has five moving parts, split between RAM and disk.
| Piece | Where | What it is |
|---|---|---|
| WAL | Disk | Append-only log of every write, for crash recovery |
| Memtable | RAM | Sorted in-memory structure (a skip list or balanced tree) that takes new writes |
| SSTable | Disk | "Sorted string table": an immutable, sorted file created when the memtable is flushed |
| Bloom filter | RAM | One per SSTable. Quickly says "this key is definitely not in this file" |
| Compaction | Background | Merges SSTables into fewer, larger ones and drops stale data |
Write path#
Insert four keys and watch the memtable after each one:
| Write | Memtable afterwards (sorted) |
|---|---|
put user_5 = "Alice" |
user_5: Alice |
put user_2 = "Bob" |
user_2: Bob, user_5: Alice |
put user_8 = "Charlie" |
user_2: Bob, user_5: Alice, user_8: Charlie |
put user_1 = "Diana" |
user_1: Diana, user_2: Bob, user_5: Alice, user_8: Charlie |
Each write is acknowledged as soon as it is in the WAL and the memtable. Whatever the insert order, the memtable keeps keys sorted, which is why it uses a skip list or balanced tree.
When the memtable reaches its size limit (a few MB, say), it is written to disk in one go as SSTable 1 (immutable, sorted):
| user_1 | user_2 | user_5 | user_8 |
|---|---|---|---|
| Diana | Bob | Alice | Charlie |
That is one sequential write. The memtable is then cleared for new writes.
More writes arrive, including an update to an existing key:
put user_3 = "Eve"put user_5 = "Alice_UPDATED"put user_6 = "Frank"
The memtable fills again and is flushed as SSTable 2 (newer):
| user_3 | user_5 | user_6 |
|---|---|---|
| Eve | Alice_UPDATED | Frank |
user_5 now exists in both files. SSTable 2 holds the correct, newer value. SSTable 1 holds a stale one. Nothing was overwritten in place.
Read path#
A read checks the memtable first, then SSTables from newest to oldest, and stops at the first match.
| Step | Read user_5 |
Read user_1 |
|---|---|---|
| 1. Memtable | Miss | Miss |
| 2. SSTable 2 (newest) | Found "Alice_UPDATED", return it |
Miss |
| 3. SSTable 1 (oldest) | Not checked: the newest value wins | Found "Diana" |
This is why reads are slower than in a B-tree: a key might be in any of several files, so the more SSTables there are, the more places you may have to look.
Bloom filters: skipping files that can't have the key#
A bloom filter is a small bit array plus a few hash functions, kept in RAM for each SSTable. It answers one question: "could this key be in this file?"
- "Definitely not": always correct. Skip the file.
- "Maybe": usually correct but sometimes wrong (a false positive). Check the file.
- It never says "definitely not" for a key that is actually there. There are no false negatives.
Building one#
Say an SSTable holds apple, cherry and grape, the filter has 10 bits, and there are 3 hash functions. Each key sets the bits its hashes point to:
| Step | Key | Hashes to bits | Bit array afterwards |
|---|---|---|---|
| Start | [0,0,0,0,0,0,0,0,0,0] |
||
| 1 | apple |
2, 5, 8 | [0,0,1,0,0,1,0,0,1,0] |
| 2 | cherry |
1, 5, 9 | [0,1,1,0,0,1,0,0,1,1] |
| 3 | grape |
3, 7, 8 | [0,1,1,1,0,1,0,1,1,1] |
Checking a key#
To check a key, hash it and look at those bits:
| Key | Bits checked | Result |
|---|---|---|
mango |
h1 = 4, and bit 4 is 0 | Definitely not here. Skip the file |
apple |
2, 5, 8 are all 1 | Maybe here. Read the file to confirm |
Why false positives happen#
Take banana, which was never inserted:
- It hashes to bits 1, 3 and 8.
- All three are 1, set by
cherry,grapeandapple. - The filter says "maybe", so you read the file.
- The key isn't there: one wasted disk read.
If a key was inserted, all of its bits were set, so a false negative is impossible. The occasional false positive just costs one unnecessary read, and a larger bit array makes them rarer.
What it saves#
Reading mango across 4 SSTables shows the payoff:
Work to learn mango doesn't exist |
|
|---|---|
| Without bloom filters | 4 disk reads |
| With bloom filters | 4 checks in RAM, 0 disk reads |
A bloom filter's lifecycle follows its SSTable:
- Built when the SSTable is flushed.
- Stored alongside it on disk and loaded into RAM.
- Deleted when compaction removes that SSTable.
- Reloaded from disk on restart.
Compaction: cleaning up#
SSTables pile up over time and reads slow down. A background process merges them, much like the merge step of merge sort. Here is SSTables 1 and 2 merged into one file:
| Key | SSTable 1 (old) | SSTable 2 (new) | Merged result |
|---|---|---|---|
| user_1 | Diana | Diana | |
| user_2 | Bob | Bob | |
| user_3 | Eve | Eve | |
| user_5 | Alice | Alice_UPDATED | Alice_UPDATED (newer wins) |
| user_6 | Frank | Frank | |
| user_8 | Charlie | Charlie |
Once the merged file is written, the old files are deleted.
Reads now check one file instead of two. The cost is CPU and disk I/O spent in the background, a trade of background work for read speed.
Deletes: tombstones#
SSTables are immutable, so you can't remove a key from one. Instead you write a tombstone, a marker meaning "this key is deleted":
| Step | What happens |
|---|---|
delete user_2 |
The memtable stores user_2: TOMBSTONE, later flushed to SSTable 3 |
read user_2 |
SSTable 3 has a tombstone, so report "not found" and don't look in older files |
| Compaction | The tombstone and the old value are both dropped |
Crash safety: the write-ahead log#
The memtable lives in RAM, so a crash would lose it. Every write therefore goes to two places:
- Appended to the WAL on disk (sequential, cheap).
- Inserted into the memtable in RAM.
After a crash, the database replays the WAL to rebuild the memtable. Once a memtable is safely flushed to an SSTable, its part of the WAL can be discarded.
The whole picture#
Put together, each operation follows a short, fixed path.
Write#
- The client's write goes to the WAL (disk) and the memtable (RAM), then is acknowledged.
- When the memtable is full, it is flushed as an SSTable (one sequential write).
- In the background, compaction merges SSTables.
Read#
- Check the memtable.
- Check SSTables from newest to oldest, skipping files whose bloom filter says no.
- Return the first match.
Delete#
- Write a tombstone.
- Compaction later removes the tombstone and the old value.
Why this suits write-heavy workloads#
Picture tens of thousands of writes per second. With a B-tree, each write means finding and rewriting a page somewhere on disk, plus every index. On spinning disks that random I/O quickly becomes the bottleneck.
With an LSM tree, each write is a memory insert plus a log append, and disk writes happen later in big sequential batches. That is why event logging, messaging, metrics and time-series systems often choose LSM-based stores.
| B-tree | LSM tree | |
|---|---|---|
| Writes | Update in place (random I/O) | Append and flush in batches (sequential I/O) |
| Reads | One tree walk | Memtable plus possibly several SSTables (bloom filters help) |
| Background work | Little | Compaction |
| Best for | Read-heavy and mixed workloads | Write-heavy workloads |
Key takeaways#
- LSM trees buffer writes in a sorted in-memory memtable and flush them as immutable sorted SSTables.
- Turning random writes into sequential ones makes writes cheap. Reads may need to check several files.
- Bloom filters in RAM let reads skip SSTables that definitely don't hold the key.
- Compaction merges SSTables and drops stale values and tombstones.
- A write-ahead log makes the in-memory memtable crash-safe.