TAOCP 6.2.4 Exercise 1
The search for $613$ proceeds from the root by repeated comparison with the keys in each visited node, following the rightmost pointer at each step since $613$ exceeds every key encountered in Fig.
Exercise 1. [10] [10] What B-tree of order 7 is obtained after the key 613 is inserted into Fig. 30? (Do not use the overflow technique.)
Verified: no
Solve time: 1m
The search for $613$ proceeds from the root by repeated comparison with the keys in each visited node, following the rightmost pointer at each step since $613$ exceeds every key encountered in Fig. 30. The search therefore reaches the unique level-$l-1$ node whose rightmost key is $607$, that node being the one whose interval of keys is maximal.
The key $613$ is inserted into this node in its symmetric position after $607$, preserving increasing order of keys within the node. The resulting node contains one additional key but still satisfies the bound of at most $m-1=6$ keys for a B-tree of order $7$, so no split occurs and no pointer changes propagate upward. All other nodes remain unchanged, and all leaves remain at level $3$. This completes the construction of the resulting B-tree. ∎