Visual walkthrough — B-tree and B+ tree — motivation (disk storage), properties

Before we touch a single symbol, let us agree on the picture and the words.

---

Step 0 — The vocabulary we will actually use

We will use exactly two rules from the parent definition, nothing more:

Why these and not the others? Because to prove the tree is short, we ask: "What is the tallest a tree could possibly get?" A tree gets tall when boxes are as empty as the rules allow — so we only care about the minimum amounts. That is why every rule above says "at least."

---

Step 1 — WHAT makes a tree tall: empty boxes

WHAT: the left tree packs many keys per box (fat, height 1). The right tree obeys the minimum rules (skinny, height 2) for the same key count. WHY: the height bound is a promise about the worst case, so we build the worst case on purpose. PICTURE: the amber boxes on the right are only half-full — that is exactly Rule B being squeezed.

---

Step 2 — Count the boxes on each level

WHAT: each cyan number counts the minimum boxes on that level. WHY: more boxes lower down means more room for keys — we need this count to add up the keys later. PICTURE: the branching fan widens by a factor of $t$ at every step; the amber arrows show one box spawning $t$ children.

Reading the picture level by level:

depth	minimum number of boxes
$0$	$1$
$1$	$2$
$2$	$2\cdot t$
$3$	$2\cdot t^2$
$i$	$2\cdot t^{i-1}$

Let us read the general term $2t^{i-1}$ symbol by symbol:

• the $2$ is the "$\ge 2$ children of the root" from Rule C — it seeds the multiplication;
• the $t$ is the branching factor from Rule A — one factor of $t$ per level below level 1;
• the exponent $i-1$ counts how many times we multiplied by $t$ to reach depth $i$ (we start multiplying only from depth 1, hence $i-1$, not $i$).

---

Step 3 — Turn boxes into a key-count

WHAT: each level's box-count gets multiplied by $t-1$ keys-per-box. WHY: this converts "how many boxes" into "how many keys," which is what $N$ actually measures. PICTURE: the amber tag on each box reads "$t-1$ keys" — the minimum load.

Adding the root's single key plus every level from depth $1$ down to the bottom depth $h$:

$N\ge \underset{\text{root’s key}}{\underbrace{1}}+\underset{\text{keys per box}}{\underbrace{(t-1)}}\underset{\text{total boxes below the root}}{\underbrace{\sum _{i=1}^{h}2t^{i-1}}}$

Reading it piece by piece:

• $N$ on the left is the real key count; the $\ge$ says the real tree holds at least this much, because we assumed everything is minimally filled;
• the lone $1$ is the root contributing its single guaranteed key;
• $(t-1)$ pulled out front is the keys-per-box factor, the same for every non-root box;
• the sum ${\sum }_{i=1}^h$ adds the box-counts of levels $1,2,\dots ,h$, where $h$ is the depth of the bottom (leaf) level.

---

Step 4 — Collapse the sum (why a geometric series appears)

The geometric-series shortcut is:

${\sum }_{i=1}^h{t}^{i-1}=\frac{t^h-1}{t-1}$

• the left side is $1+t+t^2+\cdots +t^{h-1}$ (the exponent runs $0$ up to $h-1$);
• the right side is the shortcut: numerator $t^h-1$, denominator $t-1$ — no adding required.

Plug it into Step 3 (the constant $2$ rides along outside the sum):

$N\ge 1+2(t-1)\cdot \frac{t^h-1}{t-1}$

Now watch the cancellation:

• the $(t-1)$ we multiplied by, and the $(t-1)$ in the denominator, are the same number, so they cancel;
• what survives is $1+2(t^h-1)$.

$N\ge 1+2(t^h-1)=1+2t^h-2=2t^h-1$

WHAT: we compressed the whole tree's key count into the tidy $2t^h-1$. WHY: with a single $t^h$ we can now solve for $h$ using a logarithm. PICTURE: see below — the staircase of level-sums flattening into one bar.

---

Step 5 — Solve for the height (why a logarithm, and which one)

Rearrange $N\ge 2t^h-1$ to isolate $t^h$:

$N+1\ge 2t^h⟹t^h\le \frac{N+1}{2}$

• we added $1$ to both sides to clear the $-1$;
• we divided both sides by $2$ to leave $t^h$ alone.

Now apply ${\log }_t$ to both sides — since ${\log }_t$ is increasing, the $\le$ direction is preserved:

$\boxed{h\le {\log }_t\left(\frac{N+1}{2}\right)}$

• $h$ is the tree's height (bottom depth) — the number of disk reads a lookup costs;
• ${\log }_t(\cdot )$ pulled $h$ down from the exponent, answering "$t$ to what power?";
• the argument $\frac{N+1}{2}$ is the $N$-side we isolated.

WHAT: the height is at most ${\log }_t$ of (roughly) $N$. WHY: because $t$ is huge (hundreds), this base makes the log tiny — the whole payoff. PICTURE: the final figure plots how flat this curve is.

---

Step 6 — Edge and degenerate cases (never leave a gap)

Case $N=0$ (empty tree). No boxes, height is undefined/$0$; there is nothing to read. The bound is vacuous and does no harm — we simply never enter the tree.

Case $N=1$ (single key). One root box, height $h=0$. Check the formula: ${\log }_t\frac{1+1}{2}={\log }_{t}1=0$. ✔ The bound gives exactly $0$ — no descent needed.

Case $t=2$ (smallest legal degree). Then $2t-1=3$ keys max, $t-1=1$ key min per box. This is the tallest a B-tree ever gets (least branching). Even here $h\le {\log }_2\frac{N+1}{2}$, i.e. only one level worse than a perfect binary tree — still logarithmic. Larger $t$ only makes the tree shorter, never taller.

Why the root is exempt. If the root also needed $\ge t-1$ keys, a tree with a single key ($N=1$) could not legally exist. The exemption is what lets tiny trees be valid — and it is exactly the lone "$+1$" term back in Step 3.

---

The one-picture summary

This single blueprint chains every step: minimum boxes multiply by $t$ each level (Step 2) → each holds $t-1$ keys (Step 3) → the geometric sum collapses to $2t^h-1$ (Step 4) → a base-$t$ log frees $h$ (Step 5) → giving a tree only ~${\log }_{t}N$ tall.

Recall Feynman: the whole walkthrough in plain words

We wanted to prove a B-tree is short. A tree gets tall only when its boxes are nearly empty, so we imagined the emptiest legal tree — every box at its minimum. Then we just counted. Level by level the number of boxes multiplies by $t$ (because each box must have at least $t$ children). Each box carries at least $t-1$ keys, so total keys is (boxes) × (keys-per-box), added over all levels. That sum is a geometric series — every term is the last times $t$ — so it has a neat shortcut, and after cancelling it becomes simply $2t^h-1$. Since $N$ must be at least that, we flipped it around: the exponent $h$ was trapped up high, and the tool that drags an exponent down is a logarithm base $t$. Out popped $h\le {\log }_t\frac{N+1}{2}$. Because $t$ is in the hundreds, that log is tiny — four-ish for a billion keys — and four is the number of slow disk reads we pay. Every corner (empty, one key, smallest $t$) checks out. Done.

Recall Quick self-test

Why does the branching multiply by $t$ and not $t-1$ per level? ::: $t$ is the minimum number of children (Rule A); $t-1$ is the minimum number of keys (Rule B). Boxes multiply by children, so the factor is $t$. Why base $t$ in the final log and not base $2$? ::: The trapped exponent sits on a base-$t$ power ($t^h$), and ${\log }_t$ is the exact inverse of "$t$ to a power." For $N=1$, what does the bound give? ::: ${\log }_t\frac{1+1}{2}={\log }_{t}1=0$, matching a single root box of height $0$.

---

See also: Binary Search Tree, AVL Tree, Red-Black Tree, Disk and Memory Hierarchy, Database Indexing, File Systems, Big-O Notation.