How indexes work (B-trees)
You already know an index lets the database jump to a row instead of reading every one — like the page-finder at the back of a book. Now let's open the hood. The real shape a database keeps an index in is a B-TREE: a short, wide, always-balanced tree where each node holds many keys at once. That shape is the whole reason a lookup over a BILLION rows still finishes in a few steps. Let's see why short + bushy = fast.
Reminder: scanning every row is the slow nightmare
Without any index, finding one row means a full table scan: read row 1, nope, row 2, nope, all the way down. On a million rows you might read a million rows. In big-O that's O(n) — twice the rows, twice the work. Fine for a tiny table, a disaster for a huge one. An index exists to kill that scan. The 'database indexes' topic introduced the idea as a small sorted list you binary-search. That's the right first picture. But a plain sorted list has a problem at real scale, and fixing that problem is exactly what a B-tree does. So let's go deeper.
A real index is a B-tree: short, bushy, balanced
Picture a tree, but not the skinny kind. A B-tree is deliberately SHORT and BUSHY: each node holds many keys, not just one. The top node (the root) holds a handful of signpost values — say 30 and 60. Those signposts split everything into ranges: 'less than 30 goes left', '30 to 60 goes to the middle child', 'over 60 goes right'. To find the value 45, the database reads the root, sees 45 is between 30 and 60, and follows the middle child. That child either holds 45 or points to the next level down. Because each node holds many keys, the tree only needs a few LEVELS to cover a vast number of values — and finding any value is just walking from the root down to a leaf, one level at a time. A handful of hops, no matter how huge the table.
Why bushy + balanced = few disk reads = fast
Here's the magic. Because every node is fat with keys, the tree grows WIDE before it grows TALL. A node holding hundreds of keys means hundreds of children, so just 3 or 4 levels can address billions of rows. The number of levels you walk grows like O(log n) — when the table gets ten times bigger, you add barely a level, not ten times the work. Compare that to the O(n) scan that doubles when the table doubles. That gap is everything at scale. The other half is 'always balanced'. The database keeps every leaf at the SAME depth, so no value is hiding down a long lopsided branch — every lookup costs the same small number of hops. And each hop is one read from disk; keeping the tree short means a lookup touches only a few disk reads instead of millions. Short tree, few reads, fast answer. That's why the index is a B-tree and not just any tree.
The catch: indexes cost space and slow writes
If indexes were free the database would index every column and be done. They aren't. An index is an extra structure living alongside the table, so it eats extra storage — one more B-tree per indexed column. The bigger cost is WRITES. Every time you insert, update, or delete a row, the database doesn't just touch the table — it must also slot the new key into the B-tree in the right place to keep it sorted and balanced. Sometimes a node gets too full and has to SPLIT, pushing a key up to the parent (that's exactly what the paired animation shows — a B-tree growing by splitting). All that bookkeeping makes writes slower. So the rule: index the columns you SEARCH by a lot, and don't index columns you rarely look up — each index is rent you pay on every single write.
Watch it grow: the B-tree insert animation
Reading about a balanced tree is one thing; watching it stay balanced is another. The paired animation (the 'btree-insert' concept) drops keys into a B-tree one by one. Watch what happens when a node fills up: it SPLITS down the middle, the middle key floats up to the parent, and the tree stays short and balanced instead of growing a long skinny branch. That splitting move is the secret to how a B-tree keeps every leaf at the same depth no matter what order keys arrive in — and it's also exactly the write cost we just talked about. Play it, and the words above turn into a picture you can see.
It's a tradeoff
| Option | 👍 Pro | 👎 Con |
|---|---|---|
| Index a column with a B-tree | Lookups on that column drop from an O(n) full scan to an O(log n) walk down a short, balanced tree — a few hops even over a billion rows. | Costs extra storage (a whole B-tree per index) and slows every write, since each insert/update/delete must re-balance the tree, sometimes splitting a node. |
| No index — scan the raw table | Writes are as fast as possible; adding a row touches only the table. No extra storage. | Every search reads the table row by row (O(n)) — fine on a tiny table, brutal as it grows to millions. |
Questions you might have
▸Why a TREE? Wasn't a sorted list (binary search) already fast enough?
A flat sorted list is great until you have to insert into it: keeping a giant list sorted means shoving everything over to make room, which is slow. A B-tree gives you the same fast sorted lookup (you still cut the search down at each level) but makes inserts cheap — you only touch one small node, and occasionally split it. The tree is a sorted list that's also easy to update.
▸What does 'balanced' actually mean and why do I care?
Balanced means every leaf is the same distance from the top — no branch is much longer than another. You care because it guarantees EVERY lookup takes the same small number of hops. An unbalanced tree could let some values hide down a long skinny branch, making those lookups slow; the B-tree refuses to let that happen by rebalancing as it grows.
▸Why does each node hold MANY keys instead of just one?
So the tree stays short. If each node held one key (like a basic binary tree), you'd need many levels and many disk reads to reach the bottom. Packing hundreds of keys per node makes the tree wide, so just 3–4 levels cover billions of rows — and fewer levels means fewer disk reads, which is the whole point.
▸I watched a node 'split' in the animation — what is that and why does it happen?
A node can only hold so many keys. When you insert one too many, the node is full, so it SPLITS into two and pushes its middle key up to the parent. That's how the tree grows taller — from the root down — which is exactly what keeps every leaf at the same depth (balanced). Splitting is the cost you pay on the inserts that overflow a node.
▸Do I need to build a B-tree myself to use an index?
Not at all. You just tell the database 'create an index on the city column' and it builds and maintains the B-tree for you forever — splitting, balancing, all of it. Understanding the shape just helps you reason about WHY a lookup is fast and why writes cost a little more.
Best read after: The relational model