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

With $t=3$: min keys (non-root) $=t-1=2$; max keys $=2t-1=5$; a node with $k$ keys has $k+1$ children.

• (a) 2 keys → equals the minimum $2$. Legal.
• (b) 5 keys → equals the maximum $5$. Legal.
• (c) 6 keys → exceeds max $5$. Illegal (this node must split).
• (d) 4 keys should have $4+1=5$ children, not 4. Illegal (broken child-count rule).

Data only in leaves + linked leaves for sequential scans = the B+ tree. In a plain B-tree, records can sit in internal nodes and there is no leaf chain.

(b) number of block reads. The CPU compares keys in nanoseconds; a disk block read is ~$10^4$–$10^5$ times slower. See Disk and Memory Hierarchy. Everything about B-trees is designed to cut block reads, not comparisons.

Use the parent's bound $h\le {\log }_t\left(\frac{N+1}{2}\right)$. $h\le {\log }_{50}\left(\frac{10^6+1}{2}\right)={\log }_{50}(500000.5)=\frac{\ln 500000.5}{\ln 50}\approx \frac{13.122}{3.912}\approx \mathrm{3.35.}$ Height is an integer, so $h\le 3$. At most 3 edges → at most 4 disk reads.

Entries per block $\approx 8192/32=256$. Treat that as the max number of children $2t$: $2t\approx 256⟹t\approx 128.$ So pick $t\approx 128$ → up to $2t-1=255$ keys per node, one node = one block. This is exactly the parent's rule: block size dictates fanout.

$h\le {\log }_{128}\left(\frac{10^9+1}{2}\right)=\frac{\ln (5\times 10^8)}{\ln 128}\approx \frac{20.03}{4.852}\approx \mathrm{4.13.}$ So $h\le 4$, giving at most 5 block reads for any of a billion keys — compared with ~30 for a binary Binary Search Tree.

With min 1 key per node, each node has as few as $2$ children — the tree degenerates toward binary. Worst-case height $\approx {\log }_{2}N={\log }_{2}10^6\approx 19.9$, i.e. up to ~20 levels. Compare with Q4's guaranteed $h\le 3$ when nodes are half-full ($t=50$). Conclusion: the "$\ge t-1$ keys" rule forces every node at least half full, which keeps the effective branching factor high and the height at ${\log }_{t}N$ instead of ${\log }_{2}N$. The rule is what makes the tree short.

• B-tree internal fanout $\approx 4096/96=42.6\to 42$ children.
• B+ tree internal fanout $\approx 4096/24=170.6\to 170$ children. Because B+ internal nodes carry no data payload, they pack ~4× more routers per block. Height scales as ${\log }_{\text{fanout}}N$, so higher fanout → shorter tree → fewer reads. This is the structural reason Database Indexing engines prefer B+ trees.

No. In a B+ tree the internal 40 is only a router — the real record for 40 lives in a leaf. You must descend to the leaf to read the data. (Contrast: in a plain B-tree, a key match can end at any node because the record sits there.)

$t=2\Rightarrow$ max keys $=3$, split on the 4th. "Split-on-the-way-down": when you meet a full node, split it first (median goes up), then descend.

1. Insert 10, 20, 5 → root [5 10 20] (full).
2. Insert 6: root is full → split, median 10 up. Tree: [10] over [5 6] and [20]. Insert 6 lands in left leaf [5 6].
3. Insert 12 → into [20] → [12 20].
4. Insert 30 → [12 20 30] (full leaf).
5. Insert 7 → into [5 6] → [5 6 7] (full leaf).
6. Insert 17: descend right; leaf [12 20 30] is full → split, median 20 up to root → root [10 20]; 17 lands in [12 17]. Final tree: root [10 20]; leaves [5 6 7], [12 17], [30]. All leaves at depth 1. ✓ (matches the figure)

All real keys live in chained leaves; internal nodes are pure routers. Leaves (sorted, chained): [5 6 7] ⇄ [10 12 17] ⇄ [20 30]. Routers above: [10 20]. Range 6..17: descend once to the leaf containing 6 → [5 6 7] (read 1), grab 6,7; follow the leaf link to [10 12 17] (read 2), grab 10,12,17; next key 20 > 17, stop. Answer: 2 leaf blocks read — sequentially, no climbing back to the root. That leaf chain is why range scans are cheap.

For $t=3$, $t-1=2$. If the root also needed $\ge 2$ keys, then a tree storing a single key would be illegal — yet a one-key tree obviously must exist (you just inserted your first key!). The smallest legal non-empty tree is a single root node with 1 key, e.g. [42], height $h=0$. Hence the root is exempt: it may hold as few as 1 key. Every other node still obeys $\ge t-1$. This exemption is exactly what lets a fresh tree of size 1 be valid.

(a) Max height = sparsest tree. Bound: $h\le {\log }_t\frac{N+1}{2}={\log }_3\frac{41}{2}={\log }_{3}20.5=\frac{\ln 20.5}{\ln 3}\approx \frac{3.020}{1.099}\approx 2.75\Rightarrow h\le 2$. (b) Min height = densest tree. Every node full ($2t-1=5$ keys, $2t=6$ children). Keys held by a tree of height $h$ where every node is full: total nodes $=1+6+6^2+\cdots +6^h=\frac{6^{h+1}-1}{5}$, each with 5 keys → keys $=6^{h+1}-1$.

• $h=0$: $6^1-1=5$ keys (too few for 40).
• $h=1$: $6^2-1=35$ keys (still $<40$).
• $h=2$: $6^3-1=215$ keys ($\ge 40$). So min height $=2$. Here max and min height both equal 2 — with $t=3$ and 40 keys the tree is forced to exactly height 2. Neat coincidence that shows how tight the bounds squeeze.

(a) An empty tree stores nothing; by convention it has no nodes (or a single empty root), so there is no root-to-leaf path — height is undefined/$-1$; the first insert creates a height-0 single-node tree. (b) As $t\to \infty$, one node can hold all $N$ keys → the tree collapses to a single node, $h=0$. (Real life stops this because a node can't exceed one disk block.) (c) Smallest legal $t$ is $t=2$ (1–3 keys, 2–4 children) — the 2-3-4 tree, which is structurally equivalent to a Red-Black Tree. Below $t=2$ nodes could be too empty to guarantee balance.

A B-tree with $t=64$ storing $10^{12}$ keys — worst-case reads? ::: $h\le {\log }_{64}(5\times 10^{11})\approx 6.5\Rightarrow h\le 6$, so at most 7 block reads. See File Systems and Database Indexing for real deployments.