Question

In a B+- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes: \( A = (49, 77, 83, -) \)
\( B = (7, 19, 33, 44) \)
\( C = (20^*, 22^*, 25^*, 26^*) \)
The *-marked keys signify that these are data entries in a leaf. Assume that a pointer between keys \( k_1 \) and \( k_2 \) points to a subtree containing keys in \([ k_1, k_2 )\), and that when a leaf is created, the smallest key in it is copied up into its parent. A record with key value 23 is inserted into the B+- tree. The smallest key value in the parent of the leaf that contains 25* is ___________ . (Answer in integer)

Hint:

When inserting in a B+-tree, if a node overflows, it splits, and the smallest key of the new right node is pushed up.

Answer 1

Correct Answer: 33

When the key 23 is added, it must be placed in the leaf that already contains the keys \((20^*, 22^*, 25^*, 26^*)\). After insertion, this leaf temporarily holds five keys, which is not allowed.

To restore validity, the keys are redistributed into two adjacent leaves. The left leaf keeps the smaller keys, while the right leaf keeps the larger ones. The boundary key separating these two leaves is passed upward.

This boundary value becomes a new entry in the parent node. As a result, the parent now holds more keys than permitted.

The parent node is therefore divided into two parts, and the separating key between these two parts is promoted further upward. This promoted key is the one that determines the final change at the root level.

The key that ultimately moves upward after all required adjustments is:

\(\boxed{33}\)