Q12 — What is an LSM tree — why do some databases choose it over a B-tree?

What problem does a B-tree have for writes?

A B-tree is excellent for reads. To find a row, you traverse the tree in O(log n) and land exactly on the data you need, touching only a few disk pages.

But writes are a different story. When you insert or update a row in a B-tree, you must:

1. Traverse the tree to find the correct leaf node — several disk reads
2. Write the new or updated data into that specific leaf node — a disk write to a specific location
3. If the node is full, split it and update the parent — additional random writes

The key phrase is "specific location." Every write to a B-tree is a random write — the data must go to wherever that particular node lives on disk, not wherever happens to be convenient.

Random writes are the worst thing you can do to disk hardware. On a spinning hard disk, each random write requires physically moving a read/write head to the right track — a mechanical operation that takes 5–10ms. A database doing thousands of random writes per second on an HDD would spend most of its time waiting for the disk to seek. Even on SSDs, random writes cause write amplification: the SSD's internal flash management must erase and rewrite entire erase blocks (often 256KB) even if you only changed one byte in a 4KB page. Over time, this accelerates SSD wear and degrades performance.

For workloads dominated by writes — logging, time-series data, event streams, analytics ingestion — this write amplification is the critical bottleneck.

What is the core insight of the LSM tree?

The Log-Structured Merge tree (LSM tree) is built on one fundamental observation: sequential writes are dramatically faster than random writes on every storage medium.

On an HDD, sequential writes avoid seek time — the head stays in place and writes continuously. On an SSD, sequential writes minimize write amplification — pages are filled completely before being retired. The difference in throughput is 10x to 100x depending on the hardware.

So what if, instead of writing to the exact location a row belongs in the sorted tree, you just... wrote sequentially, always at the end? And then figured out the sorted order later?

That's the LSM tree.

How does an LSM tree actually work?

Step 1: Write to memory (MemTable)

All incoming writes go into an in-memory data structure — typically a red-black tree or skip list — called the MemTable. This is sorted in memory, making it fast to insert into and fast to read from. The MemTable is also append-logged to a WAL on disk for crash safety (more on WAL in Q13).

Every write is just a memory operation. No disk seek, no random write. Thousands of writes per second are trivially handled.

Step 2: When the MemTable fills, flush it to disk as an SSTable

When the MemTable reaches a size threshold (say, 64MB), it is flushed to disk as an SSTable (Sorted String Table) — an immutable, sorted file. Because it's sorted in memory first, the flush is a single sequential write from start to end of the file. One pass, all sequential.

Once the SSTable is written, a new empty MemTable takes over for incoming writes.

Step 3: SSTables accumulate and are compacted

Over time, multiple SSTables accumulate on disk. New SSTables may contain updates to rows that exist in older SSTables. The LSM tree resolves this by using the newest value: when reading, you check the MemTable first, then the newest SSTable, then older ones. The first match wins.

But having many SSTables makes reads slow — you might check 10 SSTables before finding a row (or confirming it doesn't exist). To fix this, a background process called compaction periodically merges SSTables together: take two or more SSTables, merge-sort their contents (keeping only the newest value for each key), and write a new, consolidated SSTable. The old SSTables are then deleted.

Compaction is always sequential — reading from multiple files sequentially and writing one output file sequentially. No random I/O.

How do reads work in an LSM tree?

Reading from an LSM tree is more complex than a B-tree. To find a key, you must check:

1. The MemTable (in memory — very fast)
2. The most recent SSTable
3. The next most recent SSTable
4. ...and so on until you find the key or exhaust all SSTables

In the worst case, if a key doesn't exist, you check every SSTable. This is why LSM trees have higher read amplification than B-trees.

Two optimizations mitigate this:

Bloom filters: Each SSTable has a bloom filter — a compact probabilistic data structure that can quickly answer "is this key definitely NOT in this SSTable?" If the bloom filter says no, you skip that SSTable entirely without any disk read. Bloom filters have zero false negatives: if the key isn't there, the filter will always say so. They may have false positives (rarely saying a key might be there when it isn't), but these are uncommon and just add one wasted disk read.

Block indexes: Each SSTable has an index of its key ranges (what's the minimum and maximum key in this file? What's the minimum key in each 4KB block?). This lets you skip SSTables whose key range doesn't contain what you're looking for, and jump directly to the right block within an SSTable.

What is the fundamental trade-off between LSM and B-tree?

B-tree:

• Writes are random → slower write throughput, more wear on SSDs
• Reads are fast → single tree traversal, direct to the data, O(log n)
• Best for: read-heavy workloads, OLTP databases with mixed read/write

LSM tree:

• Writes are sequential → extremely high write throughput
• Reads are more complex → check MemTable + multiple SSTables (mitigated by bloom filters)
• Compaction in the background adds write amplification at the storage level (though still less than B-tree random writes)
• Best for: write-heavy workloads, time-series, event logging, analytics ingestion

This is why different databases make different choices. PostgreSQL and MySQL use B-trees because they serve OLTP workloads where reads are frequent and latency matters. Cassandra, RocksDB, LevelDB, and InfluxDB use LSM trees because they're optimized for ingesting high-volume writes quickly.

What does "write amplification" mean in compaction?

Compaction is the hidden cost of LSM trees. When you compact SSTables, you're reading and rewriting data that hasn't logically changed — just because it needs to be merged into a new file. A write that was committed once might be physically written to disk 3–10 times as it moves through compaction levels.

This is LSM's write amplification — though the writes are sequential, there are more total bytes written to disk over the lifetime of the data. Different LSM implementations (leveled compaction vs tiered compaction) make different trade-offs between write amplification, read amplification, and space amplification.

The mental model

B-tree writes:
  → Find leaf node (random reads)
  → Write to exact location (random write)
  → Split if full (more random writes)
  High write latency, wear on SSDs

LSM tree writes:
  → Write to MemTable (memory, instant)
  → Flush to SSTable when full (sequential write)
  → Background compaction (sequential read + write)
  High write throughput, sequential I/O always

LSM tree reads:
  → MemTable → newest SSTable → ... → oldest SSTable
  → Bloom filter: skip SSTables that can't have the key
  Higher read latency than B-tree, mitigated by bloom filters

Choose B-tree: reads matter more, OLTP, mixed workload
Choose LSM:    writes matter more, time-series, logs, event ingestion, analytics

The LSM tree exists because "always write sequentially and sort it out later" is a fundamentally better fit for write-heavy workloads than "find the exact right place to write immediately."