GATE 2025 CS (CS2) – Question 57
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)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 33
Explanation
Inserting 23 overflows leaf C, and the new leaf's smallest key is copied up into B. B is full, so it splits into (7, 19) and (33, 44), with 23 moving up to A. The leaf containing 25* lies in the range [23, 33), so its parent is (33, 44) with smallest key 33.