LSM-trees

How does an LSM-tree move write cost into background merges, and when is it really write-optimized?

The constraint. Random writes are expensive and sequential writes are cheap, and the difference is big enough to restructure around. So: do not sort on arrival. Buffer writes in memory in a structure called the memtable. When it is full, flush it as a sorted, never-modified file called a sorted run (an SSTable, "sorted string table"). Reconcile the runs later in the background by compaction (merging runs into bigger ones). The work is not eliminated (Conservation of cost). It is moved from the latency path to the throughput path, where it can be scheduled, batched and run when the device is idle. That relocation is the entire idea.

The amplification arithmetic is the real content

Let T be the size ratio between levels (each level is T times bigger than the one above), N the dataset size, M the memory buffer size. The number of levels is L = log_T(N / M).

• Leveled compaction keeps one run per level. Each level's data is rewritten about T times as the level above fills it. Write amplification ≈ T × L. Read amplification ≈ L runs to consult. Space amplification ≈ 1 + 1/T, near 1.1.
• Tiered compaction accumulates T runs per level and merges them all at once into the next. Write amplification ≈ L, which is T times cheaper. Read amplification ≈ T × L. Space amplification up to T.

One parameter walks the entire RUM triangle, which makes the LSM the cleanest available demonstration that the triangle is real.

Hybrids exist because the levels are not symmetric. RocksDB runs level 0 tiered (that is where write bursts land, and you want them cheap) and everything below leveled (that is where the bytes live, and you want space amplification near 1). This is derived, not arbitrary.

# Quick calculator for the LSM trade-off (illustrative).
import math
def lsm(T, N_over_M):
    L = math.ceil(math.log(N_over_M, T))
    return {
        "leveled": {"write_amp": T * L, "read_runs": L, "space_amp": 1 + 1 / T},
        "tiered":  {"write_amp": L,     "read_runs": T * L, "space_amp": T},
    }
print(lsm(10, 1000))   # leveled write_amp 30, read_runs 3; tiered write_amp 3, read_runs 30

Correct the folklore: "LSM-trees are write-optimized"

That statement is imprecise to the point of being wrong. Compare bytes written per byte of user data. A B-tree's write amplification is page/row. An LSM's is T × L.

Row size decides which structure is write-optimized, and the crossover is computable from two numbers you already know. This is also exactly why key-value separation exists (WiscKey, RocksDB's BlobDB, Titan): store large values outside the LSM so that compaction rewrites only the keys. That restores the small-row regime artificially. Mismatch law once more: the amplification came from a granularity mismatch, so the fix is to separate the two granularities.

The read path and the filter allocation result

A point lookup checks the memtable, then each run. Each run is guarded by a Bloom filter (a small memory structure that answers "is this key definitely not in this file?", covered fully in Probabilistic structures) and by min-max bounds (the smallest and largest key in the file). With filters, the common case costs one I/O, so LSM point reads are competitive.

The folklore default, the same number of filter bits per key at every level, is provably suboptimal. The derivation is short.

• A Bloom filter with b bits per key has false-positive rate p = e^(−b·ln²2), where ln²2 ≈ 0.48.
• Expected wasted I/Os per negative lookup = Σ pᵢ over the levels i.
• Minimize that sum subject to a fixed memory budget: Σ nᵢ·bᵢ = M, where nᵢ is the number of keys on level i.
• The Lagrange condition (the standard method for minimizing with a constraint) gives pᵢ ∝ nᵢ: the optimal false-positive rate at a level is proportional to how many keys that level holds.

So the largest level, which holds (1 − 1/T) of all data, should get the highest false-positive rate and the fewest bits per key. Buying a lower rate there costs the most memory per unit bought. The gap between adjacent levels is ln T / ln²2 ≈ 2.303 / 0.480 ≈ 4.8 bits per key at T = 10. The payoff: the total false-positive rate becomes independent of the number of levels L. You remove a factor of L from read cost at zero extra memory. This is the Monkey result (Dayan, Athanassoulis, Idreos), and it is a genuine correction to what most deployments still run.

Where the LSM genuinely loses: range queries

A scan must merge iterators across all runs, and no filter helps a range predicate, because filters answer membership ("is this key here?"), not overlap ("is anything in this range here?"). A leveled LSM with L levels does an L-way merge for every scan. A tiered one does T × L. A B+tree walks a linked list. If your workload is dominated by ordered scans over recently written data, this is the structural reason to prefer a B-tree, and no tuning closes the gap.

Compaction is the collector, the manifest is the indirection

This is the Immutability law, in the same shape as an SSD's FTL and as the manifest files of table formats like Iceberg (which list which files make up the table now). The operational consequence is variance: compaction competes for the same I/O bandwidth as foreground work, producing write stalls and p99 cliffs that look nothing like the average. (Variance law.) The mitigations (rate limiting, compaction scheduling, pacing) all convert a bursty background cost into a smooth one: pay a little in the mean to buy a lot in the tail.

Bε-trees: the continuum between B-tree and LSM

The comparison above looks like a dichotomy, but it is a continuum. A Bε-tree (also called a fractal tree) is a B-tree in which each node reserves part of its space as a buffer for pending updates and the rest for child pointers. The parameter ε controls the split. At ε = 1 the node is all pointers and you have a plain B-tree. As ε → 0 the nodes are mostly buffer and behaviour approaches an LSM. So B-trees and LSM-trees are not two designs but the two endpoints of one parameterized family. This turns the "B-tree versus LSM" choice from a dichotomy into a dial.