Indexing — B-tree index, hash index, full-text: Visual walkthrough

This is the visual companion to the parent note. It leans on the ideas of Disk vs Memory I/O, B+ Tree Data Structure, and Big-O Notation — we rebuild each one from zero here.

Step 1 — What a "row lookup" actually costs

WHAT. Picture a table as a stack of boxes on a shelf. Each box is one row (one record, e.g. one user). We want the box where email = 'x'.

WHY start here. Before we can say an index is fast, we must feel how slow the no-index way is. The unit we care about is not "seconds of thinking" — it is a disk read: fetching one chunk of data off the disk. Read Disk vs Memory I/O — a disk read is thousands of times slower than a CPU comparison, so we count disk reads, and only disk reads.

PICTURE. In the figure, boxes are lined up left-to-right. To find our target we must open box 1, check, open box 2, check... every single box until we hit it. That is a full table scan.

Figure — Indexing — B-tree index, hash index, full-text

Step 2 — The core trick: a signpost that skips boxes

WHAT. Instead of opening every box, we add signposts. A signpost is a small note that says: "boxes with keys below 30 are to the left; 30 and above, to the right."

WHY this specific trick. One signpost, read once, lets us throw away half the shelf without opening those boxes. That is the entire idea of a search tree: each read we make must eliminate many boxes, not just one. A B+ Tree Data Structure is a tree of these signposts.

PICTURE. The figure shows one signpost holding the separator key $30$ . An arrow to the left is labelled "keys $< 30$ ", an arrow to the right "keys $\geq 30$ ". Following the correct arrow, we ignore the whole other side.

If each signpost only had 2 arrows, we'd halve the work each read. But disk pages let us do far better — that is Step 3.

Step 3 — Why nodes are FAT: the branching factor $m$

WHAT. A disk read never fetches one byte — it fetches a whole page (~8 kilobytes). So a node might as well hold hundreds of separator keys and hundreds of arrows, all read in that one page.

WHY it matters enormously. More arrows per node = fewer levels to fall through = fewer disk reads. We give this "arrows per node" number a name.

PICTURE. The figure contrasts two nodes read with one disk read each: a skinny node with 2 arrows, and a fat node with (here) 4 arrows. The fat node splits the shelf into 4 pieces at once, not 2.

Step 4 — Stacking levels: how many boxes can $h$ reads reach?

WHAT. Now stack the fat nodes into levels. The root is level $0$ . Its $m$ arrows point to $m$ nodes on level $1$ . Each of those has $m$ arrows to level $2$ , and so on. We count how many leaf boxes are reachable after $h$ levels.

WHY multiply. Every level multiplies the reach by $m$ , because each node at the current level fans out into $m$ new ones. Multiplication is exactly "repeated fanning-out", so the reachable count grows like a power of $m$ .

PICTURE. The figure is a small tree, $m = 3$ . Level 0: 1 root. Level 1: $3$ nodes. Level 2: $3 \times 3 = 9$ leaves. Each level's count is annotated as a power of 3.

Step 5 — Solving for the height (the central result)

WHAT. We have $N$ rows to store in the leaves. We need enough leaves, so we require $m^{h} \geq N$ . Solve this for $h$ .

WHY the logarithm appears. $m^{h}$ is exponential growth in $h$ . To undo an exponential — to ask "what power $h$ turns $m$ into $N$ ?" — the exact tool is the logarithm. That is what a log is: the inverse of a power. No other tool answers "which exponent?".

PICTURE. The figure plots $m^{h}$ (orange, exploding upward) against the flat target line $N$ (blue). The height we need is the $h$ where the orange curve first crosses the blue line — and the log is just the horizontal coordinate of that crossing.

Step 6 — Plug in a billion and watch it collapse

WHAT. Take $N = 1 0^{9}$ (a billion rows) and $m = 100$ . Compute $h$ .

WHY these numbers. They are realistic: web-scale tables reach billions of rows, and a page of keys easily fans out ~100 ways. This is the moment the abstraction pays off.

PICTURE. A bar chart: a full scan bar towering at $1 0^{9}$ reads next to a B-tree bar at height $5$ — so tiny it is barely visible. Same table, same query.

Step 7 — The degenerate case: what if $m = 1$ ?

WHAT. Push the formula to its breaking point. Suppose each node had only one child ( $m = 1$ ) — a "tree" that is really a single chain.

WHY test this. A good derivation must survive its extremes. If $m = 1$ the tree should behave like the full scan we started with — let's verify the formula agrees, so we trust it everywhere in between.

PICTURE. The figure shows the fat tree degenerating into a vertical rope of $N$ nodes — one long line, no fan-out. Below it, the formula's output blows up.

The one-picture summary

This final figure compresses all seven steps: a fat, shallow B-tree over $N = 1 0^{9}$ leaves, $m = 100$ , with the descent path highlighted — root → level 1 → ... → leaf, exactly $h = 5$ hops — beside the exploding full-scan alternative. Every arrow you follow is one disk read; five arrows reach any of a billion rows.

Recall Feynman: the whole walkthrough in plain words

Finding one row by reading every box costs $N$ reads — hopeless for a billion boxes. So we lay down signposts that each throw away a big chunk of the shelf. Because a disk read grabs a whole page, one signpost can point == $m$ ways at once== (its branching factor). Stack these signposts into levels: each level multiplies your reach by $m$ , so after $h$ levels you can reach $m^{h}$ boxes. To cover all $N$ boxes you need $m^{h} \geq N$ ; asking "what power of $m$ is $N$ ?" is the definition of a logarithm, giving $h = ⌈ lo g_{m} N ⌉$ . Plug in a billion rows and $m = 100$ : that's $lo g_{100} (1 0^{9}) = 4.5 \to 5$ reads. If $m$ were $1$ the tree becomes a useless rope and the log blows up — which is precisely why nodes are kept fat and the tree kept balanced. Five reads for a billion rows. That is the entire magic of the B-tree.

Recall Quick self-check

Why is the lookup cost $h$ and not $m$ ? ::: We read exactly one node (one page) per level as we descend, and there are $h$ levels; $m$ only affects how shallow those levels are. What tool undoes $m^{h}$ to isolate $h$ , and why? ::: The logarithm $lo g_{m}$ , because a log is by definition the inverse of a power — it answers "which exponent?". What happens to $h$ as $m \to 1$ ? ::: It diverges (infinite/undefined); the tree degenerates into an $O (N)$ chain, so databases keep $m$ large and the tree balanced.