Storage engines: B+ trees and LSM trees

A table with a billion rows lives on disk, and you ask for one of them by its key. A database finds it in a few milliseconds, and it can also take a million inserts a second without falling over. The part that makes both possible is the storage engine: the code that decides how rows are laid out on disk and how they are found again.

Disks don't hand over single values. They read and write whole pages, typically 4 to 16 KB, and a page next to the one you just read is far cheaper than one somewhere else. On a spinning disk a random read waits several milliseconds for the head to move; SSDs narrow the gap, but they still work in pages, and both are fastest when they read or write in long sequential runs. So the question a storage engine answers is: how few pages can a lookup touch, and how few can a write?

There are two classic answers. A B+ tree keeps the data sorted in place and finds any key in a handful of page reads. An LSM tree never updates in place: it collects writes in memory and writes them out in sorted batches, merging them later. This lesson builds both.

page

The unit a disk reads and writes, a few kilobytes. A storage engine's cost is counted in pages read and written, not in comparisons.

fan-out

How many children a tree node has. One page holds hundreds of keys, so a B+ tree node can have hundreds of children, and the tree stays only a few levels deep.

separator

A key in a B+ tree's internal node that only steers searches: keys below it go left, keys from it upwards go right. It is a copy; the key itself lives in a leaf.

memtable and SSTable

An LSM tree's sorted table of recent writes in memory, and the sorted, immutable files (sorted string tables) it is flushed to on disk.

compaction

Merging SSTables into fewer, larger ones, keeping only each key's newest version, in the background.

Bloom filter

A few bits per table, kept in memory, that answer "is this key in the table?" with "certainly not" or "maybe".

A binary search tree is the wrong shape for a disk. With a billion keys it is about 30 levels deep, and each level is a different page, so a lookup costs about 30 random reads. A B+ tree puts hundreds of keys in each node, one node per page. With about 1,000 children per page, three levels reach $1000 \times 1000 \times 1000$, a billion keys, and the top levels are small enough to stay in memory, so a lookup reads one or two pages from disk.

This one has order 4 (at most 3 keys a node) so it fits on screen. The root holds only separators; every key, with its row, lives in a leaf, and the leaves are linked left to right.

A B-tree, the B+ tree's parent, keeps each key exactly once, in whichever node it lands, internal or leaf. A B+ tree moves all the rows down to the leaves. Its internal pages then hold only short separators, so more fit in a page, the fan-out goes up and the tree gets shallower. That is why the indexes of PostgreSQL and MySQL's InnoDB are B+ trees.

Range queries are where the leaf links pay off. To find every key from 20 to 60, the tree descends once to the leaf where 20 would be, then follows the links, never going back up.

Before each step, say which child a key goes down to, whether its leaf overflows, and which key moves up when a node splits. Start with insert 36: its leaf is full, so watch what is copied up from a leaf and what is moved up from an internal node. Then try a few more inserts of your own.

A B+ tree updates in place: an insert rewrites the leaf page it lands in, and sometimes splits it and rewrites the parent too. Changing a 100-byte row means rewriting a whole page, at a random place on the disk, and the database also writes the change to a log first so that a crash in the middle can be repaired. Reads are excellent; random writes are the price.

Deleting shows how little the internal nodes matter to the data. Delete 30, which is also a separator in the root.

Now the other answer. An LSM tree (log-structured merge tree) never rewrites a page. A write goes into the memtable, a sorted table in memory, and is appended to a log on disk so a crash can't lose it. That log is written sequentially, the cheapest write there is. When the memtable fills, it is written out in one sequential pass as an SSTable: sorted, and never changed again. Here the memtable holds 4 entries.

The catch is reads. A key may have been written many times, and its versions sit in different tables, newest at the top. A get searches from the top down, memtable first, then L0 newest first, then each level below, and stops at the first version it meets. Two things keep that cheap: tables below L0 never overlap within a level, so a key's range rules most tables out, and each table has a Bloom filter in memory.

Deletes can't erase anything either, because the old versions sit in immutable tables. A delete writes a tombstone, a marker saying "this key is gone", which hides every older version below it. Here keys 10, 20 and 45 were deleted after their values had sunk to L2.

Compaction is merge sort's merge: the inputs are already sorted, so one sequential pass writes the merged run. It is also where the LSM tree pays for its cheap writes. Each entry is rewritten again every time it sinks a level, so the bytes written to disk can be many times the bytes put: write amplification. A get may read several tables: read amplification. Old versions take room until merged away: space amplification. No engine minimises all three; choosing one is choosing which to pay.

• Disks work in pages; sequential I/O is cheap and random I/O is not. Storage engines are judged in pages read and written.
• A B+ tree, a B-tree that keeps every key in its leaves, is shallow and fat: one page per level, all keys in linked leaves, separators as copies above. Great for reads and ranges; writes rewrite pages in place.
• An LSM tree buffers writes in a memtable, flushes immutable SSTables and merges them in compaction. Reads go newest first, skipping tables by key range and Bloom filter.
• Bloom filters say "certainly not" or "maybe": false positives, never false negatives. Deletes are tombstones, gone only when compaction reaches the bottom.
• Write, read and space amplification can't all be low: B+ trees favour reads, LSM trees favour writes.