B-Trees and LSM-Trees — The Heart of Every Database

Almost every database ever shipped sits on a B-tree or an LSM-tree. Starting from one physical fact — storage can only be written a page at a time — here is why the two designs came out opposite, what write amplification really is, and how PostgreSQL and RocksDB differ, from zero background to the knobs you actually turn.

An analogy: shelve it now, or pile it up

When new books arrive at a library there are two ways to handle them. One is to walk each book to its correct shelf and slot it into place, nudging the neighbours aside. The other is to drop it in a bin at the front desk and, once the bin fills, merge the whole bin back into the shelves in one pass.

The first way makes finding things fast forever, because the shelves stay in order. The price is work at the shelf on every single arrival. The second makes receiving fast — you just drop the book. The price is that finding something means checking both the shelves and the bin, and every so often a big reorganisation runs.

That is exactly the difference between a B-tree and an LSM-tree (Log-Structured Merge-tree). Bayer and McCreight published the B-tree in 1972 and most databases have used one ever since. O'Neil and colleagues proposed the LSM-tree in 1996 as a design that pushes writes toward pure appends. PostgreSQL, MySQL, SQLite and Oracle are B-tree systems; RocksDB, LevelDB, Cassandra, ScyllaDB and HBase are LSM systems. Essentially every database in use today stands on one of the two.

Why do two opposite answers survive for the same job — store it, then find it? The reason is physics inside the machine.

The premise: a disk cannot read one byte

One fact separates the designs: persistent storage can only be read and written in fixed blocks called pages.

Even to change a single byte, the device reads a block of several kilobytes, edits the byte inside it, and writes the whole block back. PostgreSQL treats that block as 8 KB; MySQL's InnoDB uses 16 KB by default. SSDs are worse still — internally they can only erase in much larger units called erase blocks.

So the accounting changes compared with in-memory algorithms. Runtime is decided not by how many comparisons you do but by how many pages you touched. An ordinary binary search tree is $O(\log_2 N)$ in theory, but if each node costs a page, a billion rows means thirty disk accesses. Given that a page is hundreds of times slower than memory at best, that is not usable.

The same story plays out one scale smaller inside memory, which is the subject of Cache-Friendly Code. B-trees and LSM-trees are what you get when you push that logic all the way out to the disk.

The B-tree: widen the fan-out, shorten the tree

The idea is simple: make one node as large as one page and pack hundreds of keys into it. Instead of the binary "left or right", a single page read decides "which of these several hundred intervals".

Here $h$ is the height of the tree, $N$ the number of keys stored, and $B$ the number of branches leaving one node (the fan-out). Put in words, equation (1) says that height grows not with the row count but with its logarithm in base $B$.

How large $B$ gets depends on the page size and the key size.

$$B \approx \frac{P}{k + p}$$

$P$ is the page size in bytes, $k$ the size of one key, $p$ the size of a pointer to a child page — a formula which says, in words, how many (key, pointer) pairs fit in one page. Pack 8-byte integer keys into an 8 KB page and $B$ lands in the hundreds, so even a billion keys give a height of four or five. The binary tree's thirty page reads collapse into a handful.

Watch how gently a logarithm rises next to a linear one. The height of a B-tree rides on that flattest curve.

Searching is worth spelling out too. Read the root page, pick the interval your key falls into, descend to that child, repeat until you hit a leaf. And when an insert makes the tree taller it does not grow downward — the root grows upward. Every leaf therefore sits the same distance from the root, so a B-tree stays balanced without anyone maintaining it. No unlucky insert order can produce a lopsided, slow tree, which is the biggest practical difference from a plain binary search tree.

One correction: real databases use a B+tree, not a plain B-tree. Two differences. Actual rows (or pointers to them) live only in the leaves, so internal nodes are pure signposts. And the leaves are linked side to side. The first makes $B$ larger, because signpost nodes hold more keys; the second is why a range scan walks sideways along the leaves instead of climbing the tree.