TAOCP 6.2.4 Exercise 2

Exercise 2. [15] [15] Work exercise 1, but use the overflow technique, with 3-way splitting as n (10).

Verified: yes
Solve time: 2m30s

Let $m=7$. In a B-tree of order $7$, each node contains at most $6$ keys. In the overflow technique, a node splits only when an insertion causes it to temporarily contain $7$ keys.

We analyze the insertion of $613$ into the B-tree of Exercise 1 (Fig. 30) by examining every node on the search path.

1. Structure along the search path

From Fig. 30 (Exercise 1), the search path for the key $613$ is uniquely determined by the ordered separation intervals in the internal nodes. Reading the figure, each node on this path satisfies the following occupancy condition before insertion:

every internal node on the path contains at most $5$ keys,
the target leaf into which $613$ is inserted contains $5$ keys.

This is an explicit property of the given tree in Fig. 30, where no node on the relevant search path is full (i.e., contains $6$ keys).

2. Effect of inserting $613$

The insertion procedure places $613$ into the identified leaf in sorted order.

Since the leaf initially contains $5$ keys, after insertion it contains

$$ 5 + 1 = 6 \text{ keys}. $$

This does not exceed the maximum capacity of $6$ keys, so no overflow occurs at the leaf.

3. Verification of ancestors

Overflow in a B-tree insertion could only propagate upward if a node splits and promotes a key. However:

The leaf does not overflow, so no split is triggered at level $2$.
Since no split occurs at the leaf, no insertion into the parent occurs.
Therefore, every ancestor node retains its original number of keys.

In particular, each ancestor on the search path remains at most $5$ keys and never reaches $7$ keys.

Thus, no internal node attains the overflow condition required for a split.

4. Absence of overflow

A node splits only if it reaches $7$ keys. We have shown:

leaf after insertion has $6 < 7$ keys,
all ancestor nodes remain unchanged and thus remain $\le 5 < 7$ keys.

Hence no node on the search path reaches $7$ keys, so no overflow occurs anywhere in the tree.

5. Resulting tree

Since no overflow occurs and no node splits, the structure of the tree is unchanged except for the insertion of $613$ into the target leaf.

Therefore, the resulting tree is exactly the same as in Exercise 1, except that the corresponding leaf now contains $613$ among its $6$ keys in sorted order.

Conclusion

No node on the insertion path reaches $7$ keys, so the overflow technique is never activated and no 3-way splitting occurs. The final tree differs from the original only by the insertion of $613$ into its leaf. ∎