TAOCP 6.2.4 Exercise 3
Let $m=101$.
Exercise 3. [23] [23] Suppose we insert the keys 1, 2, 3, ... in ascending order into an initially empty B-tree of order 101. Which key causes the leaves to be on level 4 for the first time
a) when we use no overflow?
b) when we use overflow and only 2-way splitting as in (4)?
c) when we use a B*-tree of order 101, with overflow and 3-way splitting as in (10)?
Verified: no
Solve time: 5m02s
Let $m=101$. Each node can contain at most $100$ keys and at most $101$ children.
Leaves are on level $4$ exactly when the height first becomes $4$. This happens at the first $N$ such that a height-3 tree can no longer accommodate $N$ keys under the insertion discipline.
The correct strategy in all three parts is:
$$ N_{\text{critical}} = \left(\max \text{ number of keys possible in a height-3 tree}\right) + 1. $$
The key point is that all three insertion methods have the same upper bound per node (100 keys), so the difference, if any, can only come from structural constraints. We now examine each case.
(a) No overflow (standard B-tree insertion)
A height-3 B-tree has:
- Level 1: $1$ node (root)
- Level 2: at most $101$ nodes
- Level 3: at most $101^2$ nodes (leaves)
Each node holds at most $100$ keys.
Thus the maximum number of keys in a height-3 tree is:
$$ N_{\max}(3) = 100(1 + 101 + 101^2). $$
Compute:
$$ 101^2 = 10201, $$
$$ 1 + 101 + 10201 = 10303, $$
$$ N_{\max}(3) = 100 \cdot 10303 = 1{,}030{,}300. $$
Hence the first key that forces height $4$ is:
$$ \boxed{1{,}030{,}301}. $$
(b) Overflow with two-way splitting
Two-way splitting and overflow redistribution affect how nodes split during insertion, but they do not change:
- the maximum number of keys per node ($100$),
- the maximum number of children per node ($101$).
A height-3 tree is still bounded above by:
- $1$ root node,
- at most $101$ level-2 nodes,
- at most $101^2$ leaves,
each storing at most $100$ keys.
Thus the same upper bound applies:
$$ N_{\max}(3) = 100(1 + 101 + 101^2) = 1{,}030{,}300. $$
Therefore the first key that forces height $4$ is:
$$ \boxed{1{,}030{,}301}. $$
(c) B$^*$-tree of order 101 with 3-way splitting
Correct analysis of the key issue
The previous solution was incorrect because it used minimum occupancy to estimate a maximum-capacity tree. That reverses the extremal principle.
For determining when height increases, we must compute the maximum number of keys that can still fit in height 3 under valid rules, not the minimum.
Crucial observation
In a B$^*$-tree:
- The maximum number of keys per node is still $100$ (same as B-tree).
- The B$^*$-tree constraint only changes minimum occupancy (about $2/3$ full) and splitting behavior.
- It does not reduce the maximum branching factor or maximum node capacity.
Therefore, the absolute maximum size of a height-3 tree is still achieved when every node is completely full.
Maximum configuration for height 3
A height-3 tree can still have:
- $1$ root node,
- at most $101$ nodes on level 2,
- at most $101^2$ leaves on level 3,
each holding $100$ keys.
Thus:
$$ N_{\max}(3) = 100(1 + 101 + 101^2). $$
Compute as before:
$$ N_{\max}(3) = 1{,}030{,}300. $$
Conclusion for B$^*$-tree
The first insertion that forces height $4$ is:
$$ \boxed{1{,}030{,}301}. $$
Final answers
$$ \boxed{ \text{(a) } 1{,}030{,}301,\quad \text{(b) } 1{,}030{,}301,\quad \text{(c) } 1{,}030{,}301 } $$