B-trees, visually

The big database argument on Hacker News last week was Olery’s Goodbye MongoDB, Hello PostgreSQL, about moving a set of Ruby apps off Mongo after a few years. A lot of the argument in the thread was about schemas, which matches what I’ve seen (the schema is still there, it just lives in fifteen places in your code instead of one). The comment thread, as these threads do, turned into a fight about which database is “faster”, and somewhere around the two hundredth comment I realized that a lot of the people arguing had no picture of what either database actually does when you ask it for a row.

So this is that picture, for the relational side. It’s about B-trees, because once you understand the B-tree you understand most of what an index can and can’t do for you. (Mongo’s indexes are B-trees too, for what it’s worth, both in the old storage engine and in WiredTiger, which shipped as an option in 3.0 a couple of weeks ago. The argument isn’t really about the data structure.)

Why not a binary tree

If you’ve taken a data structures class, you know the balanced binary search tree. Every node has a key and two children, and a lookup takes about log₂(n) steps. For a billion rows that’s 30 steps, which sounds great.

It’s terrible on disk. Each of those 30 nodes can be anywhere, so each step is potentially a separate random read. On a spinning disk a random read costs something like 10 milliseconds, so a single lookup could take 300ms. Even with an SSD you’re doing 30 round trips through the I/O stack to find one row. The CPU’s time is basically irrelevant. All that matters is how many times you go to the disk.

The B-tree, which Rudolf Bayer and Ed McCreight came up with at Boeing around 1970 (nobody seems sure what the B stands for, and they’ve been coy about it), fixes this with one idea. Disks read in pages anyway, so make each node a whole page and pack as many keys into it as will fit. Instead of two children per node you get hundreds, and the tree gets very wide and very short.

What it looks like

Here’s a tiny one. Real nodes hold hundreds of keys, but three is easier to draw:

Strictly this is a B+tree, which is what databases actually use. The difference from the textbook B-tree is that all the keys that point at data live in the leaves, the inner nodes only hold separator keys for routing, and the leaves are linked to each other in order. That last part is why WHERE id BETWEEN 30 AND 77 is cheap. You descend once to find 30, then walk sideways along the leaves until you pass 77, without going back up the tree.

To find 41 you read the root, see that 41 is between 30 and 60, follow the middle pointer, and find 41 in that leaf. Two page reads. In PostgreSQL the leaf entry holds a pointer, a block number and an offset (Postgres calls it the ctid), to where the row really lives in the table, which is a separate file called the heap. So it’s two reads in the index and one more in the heap.

How shallow is “shallow”

Let’s do the numbers for Postgres, with an index on a bigint column. Pages are 8KB. Each leaf entry is an 8 byte header (which holds the 6 byte pointer into the heap), plus the 8 byte key, plus a 4 byte line pointer in the page’s item array, so call it 20 bytes. Take off the page header and you get a bit over 400 entries per page, and by default Postgres fills B-tree leaves to 90% when it builds them, so let’s say about 370 per page.

With about 370 entries per leaf, and a few fewer per inner page (Postgres packs those to 70% rather than 90%, so call it 285):

Level	Pages	Covers
root	1	everything
2	~33	~30 million rows each
3	~9,500	~105,000 rows each
leaves	~2.7 million	370 rows each

That’s a billion rows in four levels. The whole index is about 22GB (2.7 million leaf pages at 8KB), but the top three levels are about 80MB, and those get hit on every single lookup, so they’re basically always in memory. In practice a primary key lookup on a billion-row table costs about one read for the leaf, if it isn’t cached, plus one for the heap page. Compare that with the 30 reads for the binary tree.

I find this genuinely surprising every time I work it out. The height of the tree grows with log base 370 of n, and log₃₇₀ of a billion is about 3.5. Add another factor of 370 rows, which you’re never going to have, and you get one more level.

Inserts and page splits

Lookups are the easy part. The reason B-trees are a bit more interesting is that they stay balanced while you insert, and the way they do it is page splits.

When a leaf is full and a new key belongs in it, the database allocates a new page, moves the top half of the keys over, and adds a separator key to the parent. If the parent is full, it splits too, and so on up. The tree only gets taller when the root splits, which is why every leaf is always at the same depth. It grows from the top, which I didn’t get for longer than I’d like to admit when I first read about it.

This is where your choice of key starts to matter, and it’s the part I most wish people knew. If your key always increases, an auto-increment id or a timestamp, every insert goes into the rightmost leaf. That page is hot and in cache, and when it fills up the split leaves the old page full and starts a new mostly empty one (Postgres has a special case for this so the left page doesn’t end up half empty). Inserts are cheap and the index stays dense.

If your key is random, a UUID say, every insert goes into a random leaf. With a 22GB index most of those leaves aren’t in memory, so each insert is a random read before it’s a write. Leaves fill up at random and split at random, so on average they sit somewhere between half and three-quarters full, and the index ends up bigger than it needs to be. We hit exactly this last year on a table of events keyed by UUID. Inserts got steadily slower as the table grew past what fit in RAM, and the index was about 40% larger than the same data keyed by a sequence. Moving to a sequential key (and keeping the UUID as a plain column with its own index, for the API) fixed most of it.

Where the rows go

I said the Postgres index points into the heap, and the heap isn’t sorted. That’s a real design choice, and MySQL’s InnoDB makes the opposite one. In InnoDB the table is a B+tree, keyed on the primary key, with the full rows sitting in the leaves (16KB pages by default). Secondary indexes then store the primary key, not a physical pointer, so a lookup by email does one tree walk to find the primary key and a second one to find the row.

The upside of the InnoDB way is that rows with nearby primary keys are physically near each other, so a range scan on the primary key reads far fewer pages. The downside is that random primary keys hurt twice as much, because now it’s the table itself that’s splitting pages, not just an index. Postgres goes the other way. Rows land wherever there’s free space, updates write a new version of the row somewhere else (that’s MVCC), and an index scan over a range can bounce all over the heap. Postgres has a CLUSTER command that rewrites the table in index order, but it’s a one-off, and the order decays as you write.

If you’ve ever been confused about why EXPLAIN sometimes picks a sequential scan over a perfectly good index, this is usually why. If the query is going to touch a good fraction of the table, a few thousand random heap reads cost more than reading the whole thing front to back. The planner knows roughly how well the table’s physical order matches each index (it keeps a correlation statistic per column) and it does the math.

The practical bits

Since this got long, here’s what I actually tell engineers on my team:

A composite index on (customer_id, created_at) is sorted by customer first, then by time within each customer. It helps WHERE customer_id = ? and WHERE customer_id = ? AND created_at > ?, and does nothing for WHERE created_at > ? on its own, because those rows are scattered across every customer’s section of the leaves. Think of a phone book sorted by last name and then first name, and then try to find everyone called John.

If a query only needs columns that are in the index, the database can answer from the index without touching the heap. Postgres has done these index-only scans since 9.2, with a caveat that it has to check the visibility map, so they work best on tables that are vacuumed and not constantly updated.

LIKE 'abc%' can use a B-tree, since it’s a range. LIKE '%abc' can’t, since there’s no place in a sorted list to start looking. (In Postgres, the prefix case also needs the text_pattern_ops operator class unless your database uses the C locale, which catches people out.)

And every index is another tree that every insert has to update, with its own splits. On one of our busiest tables we had eleven indexes, and when we checked pg_stat_user_indexes four of them had never been used since the last stats reset. We dropped them and insert latency went down by about a third.

If you want to go further, the Postgres source has a README in src/backend/access/nbtree that explains its B-tree implementation (it’s based on Lehman and Yao’s 1981 paper, which adds a “right link” to each page so readers don’t have to lock their way down the tree). It’s one of the more readable bits of database code I’ve looked at, and it makes a good follow-on to my old post on how a hash table really works, since hash indexes are the other thing people reach for and mostly shouldn’t.