One Row in a Billion: B-Trees and Database Indexes
Find one customer by email among a billion rows in a few disk reads, not minutes: why reading every row and a binary search tree are both too slow on disk, and the structure inside nearly every database index, the B-tree.
Freelancer · Data Structures · Updated
After this lesson you can
- Explain why a B-tree keeps many keys in each node
- Estimate how many levels a B-tree needs for a given number of rows
Key takeaways
- Reading a billion rows takes minutes, and a balanced binary search tree still needs about 30 slow page reads, one per level.
- Reading from disk is slow, and a whole chunk of it costs about the same as one value, so a B-tree packs many sorted keys into each node.
- A node with k keys has k + 1 children, and a search picks the gap its value falls in, like a card catalog's drawers.
- More children per node means fewer levels: with a thousand per node, three levels tell a billion rows apart.
- A B-tree stays balanced on its own, and a database index is a B-tree of a column's values.
Before this: The Sorted Import That Made Search Crawl: Why Balance Matters keeps a tree short in memory. A database's tree lives on disk, where every level costs a slow trip.
Run a query that finds one customer by email among a billion rows, and the database answers in a few milliseconds. You'll meet this whenever a query is slow and someone says "add an index", in a database class, and in interviews that ask how databases find things. This lesson is brief on purpose: you won't write the structure that does it, but you'll know what it is and why it makes a billion rows feel small.
What would you try?
Read every row. Check each customer's email until one matches. On a billion rows that takes minutes, not milliseconds, and it gets slower every time the table grows: O(n).
A balanced binary search tree. It finds a name in about log n checks, and log₂ of a billion is about 30. In memory, 30 checks are nothing. But a database's data is too big for memory, so it lives on disk, and reading from disk is slow: thousands of times slower than reading memory. Worse, a disk never hands over one value at a time. It reads a whole chunk, called a page (SQL Server and PostgreSQL use 8 KB pages), whether you wanted one value from it or all of them.
So the cost that matters isn't comparisons; it's page reads. A binary search tree of a billion rows is about 30 levels tall, and each level is its own page read: 30 slow trips for one row, each bringing back 8 KB to use one key from it.
The question that leads to it
If every read brings back a whole page anyway, what if one node filled the page? A node holding hundreds of keys would pick one of hundreds of ways down in a single read, not one of two.
The idea: a fat node
This idea was so useful that it got a name: a B-tree. A B-tree node holds many sorted keys, not one, and between and around them, links to its children: a node with k keys has k + 1 children.
A library's old card catalog works the same way. The drawers are labeled with ranges, A to C, D to F, and so on. You don't check every drawer: one glance at the labels tells you which drawer to open. Inside, guide cards split the drawer into smaller ranges, and behind the right guide card is the card you want. Three looks, and you're there, among hundreds of thousands of cards.

A search in a B-tree does the same at each node: read the node's sorted keys, find the gap the value falls into, and follow that gap's link down.

Fewer levels, fewer reads
Each level multiplies how many rows the tree can tell apart by the number of children per node. Two children per node (a binary tree) doubles it each level. A thousand children per node multiplies it by a thousand. The program below counts how many levels it takes to tell a billion rows apart for three node sizes.
long rows = 1_000_000_000;
foreach (int children in new int[] { 2, 100, 1000 })
{
int levels = 0;
long reach = 1;
while (reach < rows)
{
reach *= children;
levels++;
}
Console.WriteLine("Up to " + children + " children per node: " + levels + " levels for a billion rows");
}
Up to 2 children per node: 30 levels for a billion rows
Up to 100 children per node: 5 levels for a billion rows
Up to 1000 children per node: 3 levels for a billion rows
void main() {
long rows = 1_000_000_000L;
for (int children : new int[] {2, 100, 1000}) {
int levels = 0;
long reach = 1;
while (reach < rows) {
reach *= children;
levels++;
}
IO.println("Up to " + children + " children per node: " + levels + " levels for a billion rows");
}
}
Up to 2 children per node: 30 levels for a billion rows
Up to 100 children per node: 5 levels for a billion rows
Up to 1000 children per node: 3 levels for a billion rows
rows = 1_000_000_000
for children in [2, 100, 1000]:
levels = 0
reach = 1
while reach < rows:
reach *= children
levels += 1
print(f"Up to {children} children per node: {levels} levels for a billion rows")
Up to 2 children per node: 30 levels for a billion rows
Up to 100 children per node: 5 levels for a billion rows
Up to 1000 children per node: 3 levels for a billion rows
const rows = 1_000_000_000;
for (const children of [2, 100, 1000]) {
let levels = 0;
let reach = 1;
while (reach < rows) {
reach *= children;
levels++;
}
console.log(`Up to ${children} children per node: ${levels} levels for a billion rows`);
}
Up to 2 children per node: 30 levels for a billion rows
Up to 100 children per node: 5 levels for a billion rows
Up to 1000 children per node: 3 levels for a billion rows
const rows = 1_000_000_000;
for (const children of [2, 100, 1000]) {
let levels = 0;
let reach = 1;
while (reach < rows) {
reach *= children;
levels++;
}
console.log(`Up to ${children} children per node: ${levels} levels for a billion rows`);
}
Up to 2 children per node: 30 levels for a billion rows
Up to 100 children per node: 5 levels for a billion rows
Up to 1000 children per node: 3 levels for a billion rows
reach is how many rows that many levels can tell apart: 1, then 1,000, then a million, then a billion. Three levels means three page reads, and the top level or two are read so often that the database keeps them in memory, so finding one row among a billion often costs a single trip to disk.
In Big-O, a B-tree search is still O(log n). What changes is the base of the logarithm: log base 1,000 instead of log base 2. Big-O drops that difference, as Are Two Loops Twice as Slow? Why O(2n) Is Still O(n) explained, but your users feel it: 3 slow reads instead of 30.
Always balanced
A B-tree never becomes a line, whatever order the rows arrive in. A new key goes into the leaf where it belongs. When a node is full, it splits in two and passes its middle key up to its parent; when the root splits, the tree gets a new root and grows one level taller, at the top. So every leaf is always at the same depth.
What a database index is
An index on a column is a B-tree of that column's values, each pointing to the row it came from. A query that searches by that column walks the B-tree, a few page reads, instead of reading every row. In SQL you make one with CREATE INDEX, and a table's primary key gets one automatically.
Indexes aren't free, which is why a table doesn't have one on every column:
- each index takes disk space;
- every insert, update and delete must also update every index on the table.
In your textbook
Most databases use a variation called a B+ tree: the rows' keys all sit in the leaves, the nodes above hold only signposts, and the leaves are linked side by side, so "every order from March" can walk along the leaves without climbing back up. Your class may also describe a B-tree by its order or minimum degree: the limits on how many keys a node may hold.
The B-tree's cost card
| Operation | Big-O | Why, in everyday terms |
|---|---|---|
| Find one row by its key | O(log n), with a huge base | A few drawer labels, each picking one drawer out of hundreds |
| Insert or delete a row | O(log n) | Find its leaf, then sometimes split or merge a node on the way back up |
| Find every row in a range, such as all of March | O(log n + k), k the rows found | Find the first one, then read along in order |
The honest rivals: in memory, where following a link costs almost nothing, a fat node gains little, so the sorted maps in your language stay binary trees. And for exact matches only, some databases offer hash indexes, O(1) like a dictionary; the B-tree is the default because it also answers ranges and "sorted by", which a hash can't.
Check yourself
2 questions to try on the lesson page.
So what
When a query is slow because it reads every row, an index turns that walk into a few page reads, and now you know why: a B-tree packs hundreds of keys into each node, so a billion rows are only three or four levels deep.