How database indexes work: the B-tree under everything you shipped this week

Somewhere this week you wrote a line that ended in ->where('email', $email). You did not think about it. It came back in two milliseconds, you moved on, and that was the correct amount of attention to give it.

Underneath that line sat a data structure from 1972.

Rudolf Bayer and Ed McCreight published Organization and maintenance of large ordered indexes in Acta Informatica that year. They were solving for a machine most readers have never touched: an IBM 360/44 with a 2311 disk, where the index would not fit in memory and every page you fetched cost real milliseconds of a spinning platter. Their test data set was 100,000 keys.

That paper is still the index you get by default in PostgreSQL, MySQL, SQL Server and Oracle, and the only one SQLite has ever offered. The same structure, under the same name, doing the same job: the B-tree.

What the tutorials give you, and where they stop ​

Search for "b-tree explained" and you get a hundred versions of the same article. A drawing of a tree. The invariants: every node holds between m/2 and m keys, all leaves sit at the same depth, lookups are O(log n). Maybe an animation of a node splitting.

All correct. All useless at 2am.

What none of them do is join the drawing to the rules you already follow. You know the equality column goes first in a composite index. You know that wrapping a column in lower() makes the index vanish. You know a covering index is faster and that adding your ninth index slowed the writes down. You know these the way you know a superstition: they work, and you could not derive one from another.

They are all the same fact. The tree is sorted, it is sorted in exactly one order, and it is expensive to keep that way.

The arithmetic is the whole trick ​

Start with the number that makes B-trees boring in the best sense.

InnoDB reads and writes in 16KB pages, and a node is a page. Jeremy Cole took a real table apart with an INT primary key and measured what fits: about 1,203 child pointers in an internal page, about 468 rows in a leaf page. That ratio, the fanout, is what decides everything about reads.

Read the middle row again. A table with 600 million rows in it has a primary key three levels deep. Finding one row touches three pages.

PostgreSQL, with 8KB pages, gets to roughly the same place by a slightly different route: around 600 children per internal page and 300 entries per leaf, so three levels covers something like 108 million rows, and over 99% of the pages in the index are leaves.

That last statistic is the practical punchline. The non-leaf pages are a rounding error in size and they are touched by every single query, so on any warm database they sit in the buffer pool and stay there. Your three-page lookup is usually two memory reads and one disk read.

Those exact figures are Cole's measurements of one table with an INT key, so treat them as an upper bound: fat rows and wide keys cut the leaf fanout hard. The shape holds either way. Fanout in the hundreds means depth in the single digits, for any table you are ever going to have.

Bayer and McCreight were optimising for a device where a page fetch was catastrophic, so they built a structure that is short and fat: hundreds of children per node, and only a handful of levels to descend. Fifty-four years later the disk is an NVMe drive, random access got about three orders of magnitude cheaper, and the structure did not need to change. That is what a good data structure looks like.

One correction the tutorials owe you, and this post too: what I have described is a B+tree, where the rows live only in the leaves and the leaves are chained together. That is what every engine here actually ships. Bayer and McCreight's 1972 paper describes the B-tree, and the B+tree is the refinement that came out of using it. Everybody, including the CREATE INDEX syntax, calls the result a B-tree anyway.

Sorted once, in one direction ​

Everything else falls out of the ordering.

A B-tree on (status, created_at) is not two indexes. It is one list, sorted by status, and then by created_at within each run of equal statuses. Picture a phone book sorted by surname, then first name.

Now every rule you memorised is just a question about that phone book.

Why does the leftmost column have to be in the WHERE clause? Because you can find every Jansen in a phone book instantly, and finding everyone named Pieter means reading the whole thing. Nothing about the structure knows where the Pieters are.

This is also the rule that has quietly stopped being absolute, and the shape tells you why. Oracle has had index skip scan since 9i, MySQL since 8.0, and PostgreSQL 18 added it in September 2025. A skip scan works exactly the way you would do it by hand: find the first distinct surname, run your search inside that group, jump to the next surname, repeat.

It turns one impossible lookup into thousands of cheap ones, which is a good trade when there are twelve distinct statuses and a terrible one when there are twelve million distinct surnames. The optimiser reads the cardinality of your leading column and decides. Which sharpens the rule rather than repealing it: you pay once per distinct value sitting in front of the column you actually cared about.

Why does WHERE lower(email) = ? skip the index? The tree is sorted by email, and lower(email) is a different ordering. The database would have to apply the function to every entry to know where to look, which is the scan you were avoiding. This is what "sargable" means, and it is the reason you create a functional index instead: you sort the tree by the expression you actually query.

Why do equality columns go before range columns? Because a range leaves you inside a run of leaf entries rather than at a single point. Everything to the right of the first range predicate is sorted only within each of those entries, so it narrows what comes back without narrowing what gets read. (status, created_at) works for status = 'open' AND created_at > ?. Reverse the columns and the database walks every open ticket ever created.

Why is ORDER BY sometimes free? The leaves are a doubly-linked list in key order. If your sort matches the index, the rows arrive sorted and the sort node disappears from the plan.

Why does a covering index help so much? A normal index scan gives you a pointer, and you then go fetch the actual row, which is another page in another place. Put every column the query needs into the index and that second trip vanishes. Postgres calls this an index-only scan and lets you bolt on the payload with INCLUDE, with a caveat that tells you something real about the engine: Postgres still has to prove the row is visible to your transaction, so an index-only scan checks the visibility map first. On a table that changes constantly that map is cold, and you pay for the heap fetch anyway.

One shape. Five rules. You can stop memorising them.

The half nobody draws ​

Every tutorial diagram is a read. The tree is fixed, the arrow goes down, the row comes back.

Writes are where the structure costs you.

Insert a row and the engine has to put an entry in every index on that table, each in its own sorted position, each in a different part of the disk. When the target leaf page is full it splits: allocate a page, move half the records, update the parent. If the parent is full, that splits too, and in the worst case the split cascades to the root and the tree grows a level.

This is the mechanism behind the thing you have watched happen to a mature table. Indexes get added one at a time to fix one slow query at a time, and nobody ever removes one, because removing one feels risky and adding one felt free.

Write latency climbs and bloat accumulates faster. On Postgres specifically, autovacuum then has more index pages to clean, fires more often, and competes with your writes for the same I/O. Percona has the full cascade written up. The short version is that on a table with a lot of them, the index count dominates insert cost more than anything else you are likely to tune.

The B-tree is a trade, and the tutorials only ever show you the side you are buying.

Why this one is worth knowing ​

I keep coming back to fundamentals like this because they do not rot. The B-tree outlasted the drum, the spinning disk, three generations of ORM and every framework that ever promised you would not have to think about the database. The trie and depth-first search I used to make a word game fast are from the same era and are just as current.

There is also a more immediate reason. An agent will happily write you a migration that adds an index, and it will usually be a reasonable index. It will not tell you that the column order is wrong for the query it is meant to serve, that the index it added duplicates the leftmost prefix of one you already have, or that the table takes 4,000 writes a second.

Reviewing that migration is a five-second job if you know the shape and an act of faith if you do not, which is the whole argument for never shipping code you do not understand applied to the smallest possible diff. Data modelling is on my short list of things worth learning properly right now for exactly this reason.

Bayer and McCreight never said what the B stands for. Balanced, Bayer, Boeing, broad and bushy have all been proposed. McCreight's own answer was that the more you think about what the B means, the better you understand B-trees.

Fifty-four years on, that is still the most useful thing anyone has said about them.