B-tree and B+ tree — motivation (disk storage), properties: Foundations

This page assumes nothing. Before you read the parent note, make sure every symbol below feels obvious. We build them in the order the topic needs them.

1. What is a "key"?

Why the topic needs it: a search tree only ever compares keys. The whole game is "find the folder with tab = 57 in as few steps as possible."

Look at the figure. The red box is the root. Lines going down are edges. The boxes at the very bottom with no lines beneath them are leaves. The number of lines leaving a node is its number of children.

Why the topic needs it: a B-tree is a tree of nodes. Everything — height, splitting, balance — is described using these words.

3. $N$ , $k$ , and the branching factor $b$

Before any formula, let us name three plain quantities we will use constantly.

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

Both red trees in the figure hold the same number of leaves. The left one is binary ( $b = 2$ ) and tall. The right one is fat ( $b = 4$ ) and short. The topic's magic is making trees as fat — and therefore as short — as possible.

4. The logarithm — the tool that measures "how tall"

Now that $N$ (total keys) and $b$ (branching factor) have names, we can ask the key question: how many levels does it take?

Why the topic needs it: a tree with fanout $b$ holding $N$ keys has height about $lo g_{b} N$ . That is the whole payoff of B-trees — see Big-O Notation for why $lo g$ -height means fast.

Formula Where the parent's

$h \leq lo g_{t} \frac{N + 1}{2}$ comes from — step by step Call the height (number of levels) $h$ . We count the fewest keys a tree of height $h$ can possibly hold; if even that minimum already needs height $h$ , then $N$ keys can never force a taller tree.

Step 1 — count nodes per level (minimum-fill). The root has at least 1 key, so at least 2 children. Every deeper non-root node has at least $t$ children (the minimum from §5). So the node counts, level by level, are: $1, 2, 2 t, 2 t^{2}, \dots, 2 t^{h - 1} .$ What it looks like: each level down fans out by a factor of $t$ — a rapidly widening triangle.

Step 2 — count keys. Each non-root node holds at least $t - 1$ keys. Add the root's 1 key to $t - 1$ keys times the number of non-root nodes: $N \geq 1 + (t - 1) \sum_{i = 1}^{h} 2 t^{i - 1} .$

Step 3 — sum the series. The sum $\sum_{i = 1}^{h} 2 t^{i - 1} = 2 \frac{t ^{h} - 1}{t - 1}$ (a geometric series). Multiplying by $(t - 1)$ cancels the denominator — that cancellation is exactly why the messy $(t - 1)$ disappears: $N \geq 1 + 2 (t - 1) \cdot \frac{t ^{h} - 1}{t - 1} = 1 + 2 (t^{h} - 1) = 2 t^{h} - 1.$

Step 4 — solve for $h$ . Add 1 and divide by 2 to isolate $t^{h}$ — this is where the $\frac{N + 1}{2}$ is born: $N + 1 \geq 2 t^{h} ⟹ t^{h} \leq \frac{N + 1}{2} .$ Now take $lo g_{t}$ of both sides to undo the exponent: $h \leq lo g_{t} \frac{N + 1}{2} .$ The $\frac{N + 1}{2}$ is not magic: the $+ 1$ comes from moving the lone $- 1$ across, and the $\div 2$ comes from the root having 2 children instead of $t$ . Height is a logarithm base $t$ , so a big $t$ crushes it.

5. The parent's tuning knob: $t$ (and its limits)

Some textbooks instead use $m$ , the order, meaning "maximum children". The two are just two names for the same knob, related by $m = 2 t$ (a node's max children). We stick with $t$ because the parent does.

Look at the red node in the figure: it holds $k = 3$ keys (recall from §3 that $k$ is the number of keys inside one node), so it has $k + 1 = 4$ children.

Why the topic needs it: every property in the parent ("at least $t - 1$ keys", "at most $2 t - 1$ ", height $\leq lo g_{t} \frac{N + 1}{2}$ ) is written in these letters.

6. Sorted separators = the Binary-Search-Tree idea, generalised

Why the topic needs it: this is the "BST property generalised" the parent mentions. It is how you navigate a fat node. In a B+ tree these internal separators are only signposts — the real record still lives in a leaf.

7. Disk, block, seek — where the slowness comes from

The figure shows the speed gap as bar lengths (a log scale — each step is $\approx 100 \times$ ). RAM is a sliver; an HDD seek is a giant red bar. This gap is the enemy the whole topic fights.

8. Balanced height & "all leaves at exactly the same depth"

Why the topic needs it: property 6 in the parent ("all leaves at the same depth") is precisely what lets the §4 leaf-count — and therefore the height bound — be exact rather than approximate.

Prerequisite map

The figure below shows how the plain ideas feed into the topic. Read it top to bottom: the plain ideas (keys, nodes) feed into fanout; the disk facts force one-node-per-block, which is the fanout; logs turn fanout into a short height; and balance makes that height a guarantee. All arrows meet at the parent topic.

Equipment checklist

Cover the right side and answer aloud. If any stumps you, re-read that section.

A key is ::: the value you search by; the record is the data attached to it.
$k$ (lowercase) denotes ::: the number of keys inside a single node.
The branching factor / fanout $b$ of a node is ::: how many children it actually has.
$lo g_{b} N$ means ::: the exponent you raise $b$ to, to get $N$ (how many levels of fanout $b$ reach $N$ ).
Why does a bigger base shrink the log? ::: because each level multiplies size by more, so fewer levels reach $N$ .
In the height proof, do we use the minimum or maximum children per node, and why? ::: the minimum ( $t$ ), because the tallest possible tree happens when nodes are as empty as the rules allow.
Where does the $\frac{N + 1}{2}$ in $h \leq lo g_{t} \frac{N + 1}{2}$ come from? ::: the $+ 1$ from moving the $- 1$ across, the $\div 2$ from the root having only 2 children.
If $lo g_{t} \frac{N + 1}{2} = 3.2$ , the true height is at most ::: $⌊ 3.2 ⌋ = 3$ (round the upper bound down).
$t$ (minimum degree) controls ::: the minimum ( $t - 1$ ) and maximum ( $2 t - 1$ ) keys per non-root node.
How many keys may the root hold at minimum? ::: just 1 (or 0 if the tree is empty) — the root is exempt from the $t - 1$ rule.
A node with $k$ keys has how many children, and why? ::: $k + 1$ — $k$ fences make $k + 1$ gaps.
A block is ::: the smallest chunk of data a disk reads in one I/O (e.g. 4–16 KB).
Why is a seek the enemy? ::: it is ~10 ms on an HDD, ~ $100000 \times$ slower than a RAM access; we minimise their count.
Why do we make one node = one block? ::: a read gives a whole block free, so packing it with keys maximises fanout per read.
"All leaves at exactly the same depth" is needed because ::: it makes the §4 bottom-level leaf count exact, so the height bound is exact.
How does a B+ tree differ from a B-tree? ::: records live only in the leaves (internal nodes are signposts), and leaves are chained in a list for fast range scans.

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

1. What is a "key"?

2. A node, and a tree

3. $N$ , $k$ , and the branching factor $b$

4. The logarithm — the tool that measures "how tall"

5. The parent's tuning knob: $t$ (and its limits)

6. Sorted separators = the Binary-Search-Tree idea, generalised

7. Disk, block, seek — where the slowness comes from

8. Balanced height & "all leaves at exactly the same depth"

Prerequisite map

Equipment checklist