B-Trees or LSM-Trees: Your Database Already Chose

Think about how you keep a bookshelf.

You could keep it perfectly alphabetical. Finding any book takes seconds — you know where to look. But every new book means shuffling everything to the right of it along the shelf.

Or you could just stack new books by the door and sort them out later. Adding a book takes no time at all. Finding one means checking the pile by the door, then the pile from last week, then the shelf.

You cannot have both. Sorting is work, and the only real question is when you do it.

Every database makes exactly this choice, and almost everything surprising your database has ever done follows from which way it went.

Why the choice exists at all

Disks are much faster at reading and writing a long continuous stretch than at hopping around to scattered spots. That gap was enormous on spinning disks; SSDs narrowed it but did not close it, and added a wrinkle of their own — flash has to be erased in big blocks before it can be rewritten, so lots of tiny scattered updates cost more than their size suggests.

Meanwhile your data arrives in whatever order people happen to create it. Random.

So: the data comes in shuffled, and the disk wants things in order. Somebody has to do the sorting. Alphabetise as you go, or stack by the door and tidy later.

The alphabetised shelf: B-trees

A B-tree keeps everything sorted on disk, in fixed-size pages, and updates them in place. To save a record, find the page it belongs on, read that page, change it, write it back. If the page is full, split it in two and tell the parent.

Reading is excellent, and excellent in the way that matters most: predictably. Finding a record means starting at the top and following signposts down, and the tree is very wide, so even a billion records sit only three or four levels deep. The upper levels stay in memory. A lookup is one or two actual trips to disk.

Crucially that is the worst case as well as the typical one. There is exactly one place a record can be.

Reading a range is just as good — "everything from March to June" walks along neighbouring pages, because they are already in order.

The bill arrives when writing. Every save is a trip to one specific page somewhere on the disk, and pages are typically four or eight kilobytes. So saving a hundred bytes writes eight thousand. Then, because a half-written page during a power cut would corrupt the whole shelf, most databases first write the change to a separate log — so those hundred bytes get written twice.

Engineers call this write amplification: how many bytes actually hit the disk for each byte you asked to store. For a B-tree it is routinely ten times or more.

The pile by the door: LSM-trees

A log-structured merge-tree refuses to shuffle the shelf. New data goes into a sorted list in memory, plus a log on disk so nothing is lost in a crash. That is the entire write path: add to a log, add to memory. No hunting for a page, no reading before writing.

When the in-memory list fills up, it gets written out in one long continuous stretch as a file that is never modified again. Changing an existing record just means a newer entry in a newer file. Deleting means writing a little marker that says this is gone — charmingly called a tombstone.

Writing is dramatically faster, because every write is one smooth stretch and nothing has to be read first.

The bill arrives when reading. A record might be in memory, or in any of the files on disk, and you have to check newest-first until you find it. Without help, every read touches everything.

Two things rescue it.

A bouncer at each file. Each file gets a small memory structure that can answer "is this record definitely not in here?" with certainty. It sometimes says "maybe" when the answer is no — costing you a wasted look — but it never wrongly says no. This lets a lookup skip almost every file, and it is the reason reads work at all. Its real name is a Bloom filter.

Tidying up in the background. A process quietly merges files together, keeps the newest version of each record, and throws away the tombstoned ones. This reclaims space and limits how many files a read has to consult. It is called compaction.

Compaction is where the surprises live

Compaction generates the war stories, because it is background work competing for exactly the resources the foreground needs.

Under sustained heavy writing it can fall behind. File count grows, so reads get slower because each one checks more files. Disk usage grows, because superseded data has not been merged away yet. If it falls far enough behind, some databases deliberately slow down your writes to let it catch up — which shows up as a database that was fast for six hours and then suddenly is not, with no change in what you were asking it.

There is also a space surprise that catches everyone out. Deleted data does not free space until compaction runs. A big delete can increase disk usage in the short term, because tombstones are themselves records. A database that gets fuller when you delete from it is deeply counter-intuitive and entirely by design.

LevelDB, RocksDB, Cassandra and HBase are all LSM-trees. RocksDB in particular quietly sits underneath a surprising number of systems that never mention it.

Side by side

You cannot have both. There is even a formal version of this — the RUM conjecture — which says you can optimise for fast reads, fast updates, or small size, and improving any two costs you the third. Every database is a point on that surface, and every revolutionary new one is a different point, not an escape.

What to actually do with this

Most of the time, nothing. Take the boring default and move on. It earns its keep in three situations.

Choosing under genuinely heavy writing — a log, event ingestion, sensor readings, metrics. That is what B-trees are worst at and LSM-trees were built for, and the gap is big enough to change your architecture.

When a database mysteriously slows under sustained writes. On an LSM-tree, look at the tidying backlog before you look at your queries. It starts growing before the slowdown shows up.

When deleting makes things worse. That is tombstones, and the answer is not to delete more carefully. It is knowing the space comes back later.

Your database chose its side before you wrote a line of code. Knowing which side turns a whole category of baffling behaviour into something you could have predicted from a bookshelf.