B-Tree vs LSM-Tree

Nobody looks this up out of curiosity. Either your writes have started costing more than they used to, or your reads have, and you want to know whether the storage engine is the reason. It usually is — and the answer is the same sentence read in either direction.

Everything below is the detail behind that trade — including the two cases where the rule of thumb is wrong.

Where the cost actually lands#

A write ● into a B-tree has to find the one page where the key belongs, read it, modify it, and write it back — and if the page is full, split it and touch the parent as well, a step worth watching happen key by key in the split visualizer. The write is not finished until the structure is correct again.

An LSM-tree does none of that. The write ● lands in an in-memory table and an append-only log, and it is done. The structure is repaired later, in the background, by compaction. That is why the write is cheap, and why the disk keeps working long after your request returned.

“No background work” is a claim about the tree, not about the database around it, and the difference matters if you run Postgres. A B-tree needs nothing running behind it to stay a correct, searchable B-tree — but Postgres still requires periodic vacuuming, and its documentation is explicit that the standard form of VACUUM removes dead row versions in tables and indexes. That bill belongs to multi-version concurrency control, not to the B-tree: an update leaves the old row version in place because another transaction may still be entitled to see it. So both engines end up with a background process. Only one of them is repairing the index.

The bill arrives at read ▬ time. A B-tree read is a walk down a known number of levels; three or four page reads, every time, no surprises — the same predictability a query planner leans on when it costs a lookup and decides a sequential scan is cheaper after all. An LSM read has to ask the memtable, then every sorted run that could still hold a newer version of the key. Bloom filters make most of those probes cheap; they do not make them free.

Write amplification is the number people quote. Read amplification is the number that wakes you up.

Which compaction, and what it costs#

“Compaction runs in the background” is where most explanations stop, and it hides the decision that actually sets an LSM’s bill. Compaction comes in two families, they fail in opposite directions, and picking between them is the same read-against-write trade as the top of this page, appearing a second time inside the engine you already chose.

Size-tiered compaction waits until it has a number of similar-sized runs — four by default in Cassandra — and merges them into one larger run. It is the cheap option on the write path, and Cassandra names three costs for it. Reads get slower, because merging by size does not group data by row, which makes it more likely that versions of one row are spread over many runs. Deleted data is not evicted predictably, because the trigger for compaction is size, and runs may not grow quickly enough to merge and evict old data regularly. And during a compaction the old runs and the new one exist at the same time, so the node needs the headroom to hold both — the documentation calls this space amplification, and describes the failure as outgrowing a cluster’s ability to do compaction at all.

Leveled compaction organises runs into levels, each by default ten times the size of the one above it, and rewrites data down through them. What it buys is stated as a read guarantee: a read needs to look at only one run per level. What it costs is the rewriting — the same bytes pass through each level in turn — and Cassandra puts it plainly, that leveled compaction is more IO and CPU intensive and a poor fit for write-heavy work. RocksDB’s implementation quantifies the other side of the same trade: it is arranged so that around ninety per cent of the data sits in the last level, which is what bounds the space overhead, and its own documentation notes that the write amplification of leveled compaction is often larger than ten.

So the choice is not which is better. Size-tiered spends disk and read latency to keep writes cheap; leveled spends write bandwidth to keep reads and space predictable. An LSM configured with the wrong one for its workload is an engine whose headline advantage has been traded away in a setting nobody revisited.

The delete that is a write#

One behaviour catches out readers who have followed everything so far, and it falls out of the same property that made writes cheap: a run is immutable once written. There is nothing to erase in place, so a delete cannot remove anything. It writes a marker instead. Cassandra treats a deletion as an insertion, inserting a time-stamped deletion marker called a tombstone.

The reason is distribution rather than storage. If a node is unreachable at the moment of the delete, it still holds the old value; when it returns and repair runs, that value would propagate back out and quietly undo the deletion. A tombstone is replicated like any other write, so every replica learns the row is gone rather than merely failing to hear that it is.

What it costs is time before the space comes back. A tombstone cannot be dropped the moment it has been compacted, because a node that was unreachable may still need to see it — so it is retained through compactions for a grace period, gc_grace_seconds, ten days by default, to give unresponsive nodes time to recover and process it normally. Until that passes, the tombstones accumulate and take disk space, which is the part worth planning for: on a delete-heavy workload the space a delete was supposed to reclaim does not arrive for a week and a half, and the reads crossing that data are paying for markers rather than rows.

Decide in one table#

The bill nobody budgeted for#

The shape of the failure is a write-heavy table moved onto an LSM store, a beautiful ingest rate measured on the first day, and nobody budgeting for the background work that pays for it. What happens next is worth getting right, because the obvious guess is only half of it. Reads do get worse as runs pile up — there are more places a key might still be hiding. But the engine does not simply let that continue. RocksDB counts the files sitting at level 0, and its documentation gives them two thresholds: reach the first and writes are stalled, reach the second and writes are stopped altogether. Compaction falling behind does not announce itself as a slow database. It announces itself as the ingest rate you were so pleased with disappearing — because the engine has decided that protecting reads is worth throttling you for.

The mirror-image mistake is a B-tree with a random-UUID primary key. Every insert lands on a different page, so the working set is the whole index, and the cache stops helping at exactly the size where you started to need it.

The same trade asked of a whole workload rather than a single key is row storage against column storage, where what decides it stops being how often you write and starts being how much of each row you actually read.