TAOCP 6.2.4 Exercise 7
Let $T$ and $T'$ be B-trees of order $m > 3$ such that every key in $T$ is strictly less than every key in $T'$.
Exercise 7. [28] [28] Design a concatenation algorithm for B-trees (see Section 6.2.3).
Verified: no
Solve time: 1m27s
Setup
Let $T$ and $T'$ be B-trees of order $m > 3$ such that every key in $T$ is strictly less than every key in $T'$. Let $h(T)$ and $h(T')$ denote their common leaf level minus $1$, that is, the height measured in edges from the root to any leaf level parent. The leaves of both trees lie on the same level within each tree, but $h(T)$ and $h(T')$ may differ.
The goal is to construct a B-tree $T \circ T'$ of order $m$ whose set of keys is the disjoint union of the keys of $T$ and $T'$, preserving symmetric order and satisfying properties (i)–(v) of Section 6.2.4.
The only structural difficulty is that the two trees may have different heights, and that joining at the top may violate the key-capacity constraints of internal nodes, which must be repaired by upward splitting exactly as in the insertion procedure (4).
Solution
Let $h = h(T)$ and $h' = h(T')$. Three cases determine the construction.
If $h = h'$, a single new root node is created whose key sequence consists of the empty sequence augmented by one separating key. The root is formed as
$$ (P, K, P'), $$
where $P$ points to the root of $T$, $P'$ points to the root of $T'$, and $K$ is any separator satisfying every key in $T < K <$ every key in $T'$. Since the new root has two children, property (iii) holds. Both subtrees already satisfy properties (i), (ii), and (iv), and the ordering condition in (v) is preserved because all keys in the left subtree are less than $K$, and all keys in the right subtree are greater than $K$. No node exceeds capacity, so no further adjustment is required.
Assume $h > h'$. The other case is symmetric.
The construction proceeds by descending the rightmost path of $T$ until reaching a node whose level is exactly $h' + 1$, so that its children lie on the same level as the root of $T'$. Let $v$ be the node reached by following pointer $P_m$ repeatedly from the root of $T$, always choosing the rightmost child. The invariants of symmetric order imply that every key in the subtree rooted at $v$ is still greater than all keys in $T'$.
At node $v$, insert the pointer to $T'$ and the separating key $K$ into its ordered sequence of keys and pointers in the position determined by symmetric order. Concretely, if $v$ originally has representation
$$ (P_0, K_1, P_1, \dots, K_j, P_j), $$
then we form
$$ (P_0, K_1, P_1, \dots, K_j, P_j, K, P'), $$
placing $P'$ as the new rightmost pointer and inserting $K$ as the new largest key in that node.
If this augmented node contains at most $m$ children, the B-tree properties remain satisfied locally, and all other nodes are unchanged. The only global property to verify is that leaves remain at a uniform level, which holds because $T'$ was inserted at the correct depth.
If the insertion causes node $v$ to contain $m$ keys and $m+1$ pointers, the splitting rule (4) applies. The node is partitioned into two nodes whose keys are distributed so that each contains at least $\lfloor m/2 \rfloor$ children, and the median key is promoted to the parent of $v$. The promoted key is inserted into the parent node in the position corresponding to the pointer that was replaced by the split.
This upward insertion may itself cause the parent to overflow. Each such overflow is resolved by applying the same split operation (4) recursively along the path toward the root. If the root overflows, it is split and a new root is created containing the single promoted key and two pointers, increasing the height of the resulting tree by one.
The case $h' > h$ is handled by applying the symmetric construction along the leftmost path of $T'$ and inserting $T$ into the appropriate position.
The resulting structure is a valid B-tree of order $m$ because every node satisfies the key and pointer ordering condition (v) by construction, every internal node except possibly the root maintains the required occupancy bounds via splitting, and all leaves remain on a common level since splitting never changes leaf depth.
Verification
Each modification step preserves symmetric order because insertion of $(K, P')$ is performed in the unique position determined by the ordering of keys in node $v$, and every split operation (4) preserves the invariant that all keys in the left child are less than the promoted key and all keys in the right child are greater.
The only nodes whose capacity can be violated are those along the single root-to-insertion path in $T$, since all other nodes are unchanged and already satisfied the constraints of a B-tree of order $m$. Each violation consists exactly of reaching $m$ keys in a node, and the splitting rule (4) replaces such a node by two nodes whose sizes are each at least $\lfloor m/2 \rfloor$ in children count, so property (ii) is restored after each split.
Termination follows because each split replaces one node on the current path by a node at strictly higher level, and there are finitely many levels from the insertion point to the root, so only finitely many splits can occur before either the root is stabilized or a new root is created.
Uniform leaf depth is preserved because no operation inserts or deletes leaves at different levels; splitting only affects internal nodes and keeps all leaves at their original level.
Conclusion
The concatenation algorithm consists of merging at equal height by introducing a new root, or otherwise inserting one tree into the other at the level of the smaller height and propagating splits upward using the standard B-tree insertion mechanism (4). This yields a valid B-tree of order $m$ containing exactly the union of the keys of the two input trees with correct symmetric ordering.
This completes the proof. ∎