LSM Tree Indexes
Concept. An LSM tree buffers inserts in a RAM MemTable, flushes them to immutable SSTables, and merges SSTables in the background. The design turns random writes into sequential disk writes.
Intuition. Spotify can ingest 1 million listen events per second. A B+Tree turns each insert into a random disk write. An LSM tree accepts writes in RAM, then flushes them to disk as one sequential file. A read probes the MemTable, then probes the on-disk SSTables.
Prerequisites. SSTables introduces the immutable file format LSM trees are built from.
What Gets Stored
Every record is a (key, value, timestamp) triple. For a song-play counter, that looks like:
(S_102, +1, 13:42:05)
Song ID is the key, the increment is the value, and wall-clock time is the version. No row is ever updated in place. A new (S_102, +1, …) is appended for every play, and the "current state" of S102 is whatever you get when you add all of its values together.
Writes: How Data Moves from RAM to Disk
Writes flow downward through three tiers. The caption below names each piece and walks the live S75 example.
Figure 1. LSM write path at 1:44 PM, RAM on top and disk below, time flowing downward. Incoming plays land in the in-RAM MemTable (fast, no seek, lost on crash unless replayed from the WAL). Every 15 minutes the engine flushes it to an immutable Level-0 SSTable on disk (1:00, 1:15, 1:30). Hourly compaction merges those into one larger sorted, de-duplicated Level-1+ file. Total plays for S75 spread across tiers (+2 in the MemTable, +10, +5, and +3 in Level-0, 5,420 in compacted history) and the read path sums them to 5,440 (merge-on-read). The merge operator is configurable: "add" for counters, "newest wins" for last-write-wins keys, "set union" for tags, "max" for high-water-marks. The merge section walks through more examples.
No write ever does a random seek. The MemTable is RAM, the flush is one sequential append, and compaction is a streaming merge. This is how an LSM tree sustains a million writes per second on commodity disks.
Compaction does charge a price. Every time it merges a key into a larger level it rewrites that data, so one logical insert becomes several physical writes over its life. The ratio of physical bytes written to logical bytes written is called write amplification, and it is what wears an SSD and caps sustained write throughput.
Reads: Merge on Read
The real state of a key isn't stored anywhere. It's computed by walking every tier that might hold the key and combining the results.
Figure 2. Merge-on-read computes S75's play count at read time instead of storing it, by summing every tier that holds a fragment. The live in-RAM MemTable (red) adds +2, the three flushed Level-0 SSTables on disk (green) add +10 · +5 · +3 = +18, and the compacted Level-1+ SSTable on disk (green) adds +5,420, for a total of 2 + 18 + 5,420 = 5,440 (the merge function is "add" because plays are a counter). Each SSTable carries a bloom filter, so the reader skips any tier that cannot hold the key with no disk read, making most reads far cheaper than this worst case.
A naïve read would touch every SSTable. In practice each SSTable carries a bloom filter, so tiers that can't possibly contain the key are skipped without a disk read. Hot keys in recent SSTables answer fast, and cold keys may walk deep.
How "Merge" Is Defined
Because LSM reads compute state from fragments, the "merge" step is really an application-specific reduction. Four patterns cover most systems. The first two:
| Pattern | Merge logic | Example |
|---|---|---|
| Counter | sum(v₁, v₂, …) | Song play counts. Sum the +1 fragments. |
| Latest-wins | pick max(timestamp) | User profile updates. Newest overwrites. |
The other two keep partial state or filter by time:
| Pattern | Merge logic | Example |
|---|---|---|
| Statistical | sum(sums), sum(counts) | Rolling averages. Keep running totals. |
| TTL / retention | filter(time > now − window) | Session logs. Drop events older than 24 hours. |