Heads up: posts on this site are drafted by Claude and fact-checked by Codex. Both can still get things wrong — read with care and verify anything load-bearing before relying on it.
why → how

Why B-trees still dominate database indexes

Disks read in blocks, not bytes. B-trees were designed around that one fact — and decades later, even on SSDs, no one has dethroned them.

Data intermediate Apr 29, 2026 · updated Aug 25, 2026 · 12 min read
On this page

The picture version

Six pictures for a reader who has never opened a database, following one question: your last fifty transactions, out of a few billion rows.

1 · The problem

Storage hands you a whole page, never a byte.

WHERE account_id = 8429173 ORDER BY created_at DESC LIMIT 50 over a few billion rows, in a handful of milliseconds what the disk actually gives you one 8 KB page your 8 bytes So the question is never “how few comparisons?” — it is “how few pages?”
Reading one byte and reading the whole page it sits in cost roughly the same. The right structure is the one that minimises pages touched, not the one that minimises comparisons — and that single constraint is what a B-tree is shaped around.

2 · The naive way

A binary tree pays page prices for byte-sized answers.

… 26 more levels … ~30 levels for a billion keys one page fetch per hop and each fetch yields exactly one key ~30 pages, roughly a quarter of a megabyte to extract one key from each Thirty page fetches to answer one question about one account.
Pointers fixed the sorted array’s insert problem — one new transaction no longer rewrites gigabytes — but each hop lands somewhere else on disk. The tree got cheap to write and expensive to read.

3 · The trick

Make every node as fat as a page.

one node = one page ~500 keys, sorted binary-search inside the page you already hold in RAM, then descend to exactly one child one fetch kills 499 of 500 branches instead of 1 of 2 depth for a billion keys binary 500-way ~30 4 and in a warm database the top levels are already cached
If the storage layer is going to hand you 8 KB anyway, fill it. That one move is the whole argument — ~500 keys per node means a tree four levels deep indexes something like 500⁴ ≈ 62 billion entries. Everything after this is repair work on it.

4 · The repair

Nodes fill up, so they split.

a leaf fills up it splits in two a separator moves up … parent … no room for the new key sep pushed up half the keys each … | sep | … tree still balanced The only way the tree grows taller is the root splitting. so there is no periodic rebalancing pass — every leaf stays the same distance from the root which is what keeps it four levels deep while you keep swiping your card
A leaf that overflows splits in two and hands a separator key to its parent; if the parent overflows it splits too, and in the rare worst case the root splits and the whole tree gains one level. Balance is a consequence of the growth rule, not a maintenance job.

5 · The payoff

Data only in the leaves, and the leaves hold hands.

routing keys only routing keys only routing keys only descend your rows your rows land here once ← then walk sideways along the linked leaves No climbing back up — which is exactly why ORDER BY … LIMIT 50 is cheap.
Two changes turn a B-tree into the B+ tree databases actually ship. Internal nodes hold keys purely as routing information, which makes them denser and the tree shallower; and the leaves are linked, so fifty transactions in date order are one sideways walk rather than fifty trips through the tree. When someone says “B-tree index,” they almost always mean this.

6 · Keep this card

The whole thing on one index card.

B-tree = a sorted index with nodes as fat as a page + split on overflow, so it stays shallow + data only in linked leaves, so ranges slide the fan-out is why lookups are shallow; the linked leaves are why ranges are cheap
Picture to keep: a filing cabinet where every drawer’s front label lists five hundred name ranges — you read one label, open one drawer, and 499 of 500 possibilities are gone. Where it breaks: real drawers don’t rearrange themselves, and the self-splitting is the part that makes a B-tree a B-tree.

Why it exists

Open your banking app. Your last fifty transactions appear before your thumb leaves the screen — newest first. Somewhere on the other end, a table holding every transaction from every customer just answered WHERE account_id = 8429173 ORDER BY created_at DESC LIMIT 50, out of a few billion rows, in a handful of milliseconds. That query is the running example for this whole post: one exact-match lookup, then fifty rows in sorted order. Hold onto it.

Reading every row to find yours is obviously absurd. But the obvious alternatives are also bad. A sorted array would let you binary-search, but you’d have to rewrite huge chunks of it on every insert — and this table takes inserts constantly. A hash table gives you O(1) lookups but destroys ordering, so the ORDER BY created_at DESC LIMIT 50 half of the query goes back to scanning everything.

The deeper problem is that databases don’t live in RAM. They live on storage that is read in fixed-size blocks, and every layer between the query and the platter has its own block size: a hard disk exposes 512 B or 4 KiB sectors, an SSD reads a flash page (commonly 4 KB), the filesystem works in blocks, and the database stacks its own page on top — 8 KB in Postgres, 16 KB by default in InnoDB. What matters is that the smallest useful unit is a page, not a byte: reading one byte and reading the whole page it sits in cost roughly the same. So the right data structure isn’t the one that minimizes comparisons; it’s the one that minimizes how many pages you touch to answer the question.

B-trees are the data structure shaped exactly around that constraint.

Why it matters now

Every relational database engineers reach for in 2026 — Postgres, MySQL/InnoDB, SQLite, SQL Server, Oracle — uses a B-tree variant as the default index. So do many embedded key-value stores that need ordered iteration. When you write CREATE INDEX without specifying a type, you almost certainly get a B-tree.

That’s not because nobody tried alternatives. LSM trees power RocksDB, Cassandra, and most of the NoSQL wave. Hash indexes exist. Skip lists exist. Bitmap indexes exist. They all win on specific workloads. B-trees keep winning the default slot because the workload most applications actually have — mixed reads and writes, range queries, point lookups, ordered scans — is exactly what B-trees are tuned for.

The short answer

B-tree = sorted index + fat nodes sized to a disk page

Picture to keep: a filing cabinet where every drawer’s front label lists five hundred name ranges. You read one label, open one drawer, and 499 out of 500 possibilities are gone — four labels deep and you’re holding the one folder you wanted. Like a filing cabinet, except the drawers rearrange themselves as you file: when one gets full it splits in two and the label above it is rewritten. That self-rearranging is the part a cabinet can’t do and the part that makes a B-tree a B-tree.

A B-tree is a balanced search tree where each node holds hundreds of keys instead of one or two. That fan-out is the whole trick: with ~500 keys per node, a tree only 4 levels deep can index something like 500⁴ ≈ 62 billion entries. Four page fetches to find any row — and in a warm database the top levels are almost always already in the buffer cache, so the fetches that actually reach the disk are fewer still. Compare to a binary tree, which would need ~36 levels for the same data.

How it works

Build it from the constraint, one failure at a time. Keep the banking query in view. The index the database wants here is a composite one on (account_id, created_at) — sorted by account first, then by date within each account — so “your last fifty transactions” is a contiguous run of entries. Find the start of your account’s run, then read fifty entries sideways.

Naive attempt: keep the index as a sorted array of keys. Binary search finds the account in ~30 comparisons over a billion entries, and the range scan is free — the rows you want are already adjacent. Beautiful, until someone swipes a card. Why it breaks: one insert in the middle means shifting everything after it. A single new transaction can rewrite gigabytes.

Fix: don’t store the order in the layout, store it in pointers — a binary search tree. Now an insert touches a handful of nodes instead of the whole array. Why it breaks: each hop follows a pointer to a different place on disk, and storage hands you a whole page whether you want one or not. A billion-entry binary tree is ~30 levels deep, so a lookup pulls in ~30 pages — roughly a quarter of a megabyte at 8 KB a page — to extract one key from each. You are paying page prices for byte-sized answers, thirty times per lookup.

Fix: make each node as fat as a page. If the storage layer is going to hand you 8 KB anyway, fill it — put ~500 keys and their child pointers in one node. Load the root, binary-search inside the page you already have in RAM, and descend to exactly one child. Every page you fetch now eliminates 499 of 500 branches instead of 1 of 2. Depth drops from ~30 to 4. That’s the whole argument, and everything below is repair work on it.

Why it breaks: nodes fill up. Fix: split. When a leaf overflows, it splits into two leaves and pushes a separator key up to the parent. If the parent overflows, it splits too, and in the rare worst case the root splits and the tree gets one level taller. The tree stays balanced by construction — there is no periodic rebalancing pass, because the only way to grow is from the root.

Why it breaks: the query above isn’t done. Finding account_id = 8429173 is one thing; reading fifty transactions in date order is another. In a plain B-tree, data sits in internal nodes as well as leaves, so an in-order walk has to move between levels rather than sliding along one. And keeping data in internal nodes makes them bigger, which means fewer keys per page, which means less fan-out — the one thing you were buying.

Fix: the B+ tree. Two changes. First, only leaves hold data; internal nodes hold keys purely as routing information, which makes them denser, which raises fan-out, which lowers height. Second, leaves are linked in a list. Once you land on the first matching row, you walk sideways along the leaf list — no climbing. That is precisely why ORDER BY created_at DESC LIMIT 50 and WHERE created_at BETWEEN … AND … are cheap.

When someone says “B-tree index” in a database context, they almost always mean B+ tree. The naming is sloppy but universal.

Why fat nodes are still the right answer on SSDs

The original B-tree paper (Bayer & McCreight, 1972 — the date is well documented) was motivated by spinning disks, where seek time dominated and reading a whole track was almost free relative to repositioning the head. You’d expect SSDs, with their flat random-access cost, to break the analysis.

They don’t, for two reasons:

How large that in-memory gap is on a given CPU isn’t something a single published number settles — it moves with node size, key width, and how much of the tree fits in cache. The qualitative result is visible in what implementers choose, though: SQLite’s in-memory tables use the same B-tree code as its on-disk ones.

Show the seams

A few places where the textbook story is misleading:

You started with B-tree = sorted index + fat nodes sized to a disk page. What did this post add? — + split-on-overflow and + data only in linked leaves. The first is why the tree stays four levels deep while you keep swiping your card; the second is why your fifty transactions come back in one sideways walk instead of fifty round trips through the tree.

Check yourself

Before you go — your table’s primary key is a random UUIDv4, and inserts get slower as the table grows past RAM. Where in the chain above did that go wrong?

Answer

At the fat-nodes step. Fan-out only pays off if the pages you touch stay in cache. A random key lands in a random leaf, so each insert faults in a different page, dirties it, and eventually writes it back. Sequential keys funnel every insert into the same rightmost leaf, which stays hot. The tree depth is identical either way — it’s the cache hit rate on the leaf, not the number of levels, that fell off a cliff. Time-ordered IDs such as UUIDv7 exist partly because ordering the keys puts inserts back on a hot leaf.

And one more — a colleague says “our index is on (account_id, created_at), so a query filtering only on created_at will still be fast.” Are they right?

Answer

Usually not, and the reason is the leaf order. Entries are sorted by account_id first, so all of March’s rows are scattered across every account’s run rather than sitting together — there’s no single subtree that holds the answer, which is what descending the tree requires. The engine’s fallbacks are worse than a lookup: scan the entire index (a full scan wearing a costume), or, in recent Postgres versions, a skip scan, which walks the distinct leading values and does a sub-search under each — better than nothing, but its payoff collapses as the number of distinct account_ids grows. Column order in a composite index is not a detail.

Going deeper