GATE CS 2025 Set 2 Q.57: File Organization, B-Trees and B+ Trees Indexing

In a $\text{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 $\text{B}^+$ -tree.

The smallest key value in the parent of the leaf that contains $25^*$ is __________. (Answer in integer)

Your answer

Official answer and solution

Official answer: 33
From: Official GATE 2025 answer key

Solution

Trace the leaf split of $C$ upon inserting $23^*$ , followed by the internal node split of $B$ when the copied-up key overflows $B$ .

Insertion into leaf $C$ : Key $23^*$ belongs in leaf $C = (20^*, 22^*, 25^*, 26^*)$ (which is pointed to by the pointer between $19$ and $33$ in $B$ ). Inserting $23^*$ causes $C$ to overflow with $5$ keys $(20^*, 22^*, 23^*, 25^*, 26^*)$ .
Splitting leaf $C$ : $C$ splits into two leaves (either $(20^*, 22^*)$ and $(23^*, 25^*, 26^*)$ with $k_{\text{up}} = 23$ copied up, or $(20^*, 22^*, 23^*)$ and $(25^*, 26^*)$ with $k_{\text{up}} = 25$ copied up).
Splitting internal node $B$ : Inserting $k_{\text{up}} \in \{23, 25\}$ $k_{up} \in {23, 25}$ into parent $B = (7, 19, 33, 44)$ $B = (7, 19, 33, 44)$ gives $5$ $5$ keys $(7, 19, k_{\text{up}}, 33, 44)$ $(7, 19, k_{up}, 33, 44)$ , causing $B$ $B$ to overflow.
- In an internal node split of a $\text{B}^+$ -tree, the middle (3rd) key $k_{\text{up}}$ is pushed up into root $A$ (making $A = (k_{\text{up}}, 49, 77, 83)$ ).
- Internal node $B$ splits into left node $B_1 = (7, 19)$ (covering keys $< k_{\text{up}}$ ) and right node $B_2 = (33, 44)$ (covering keys in $[k_{\text{up}}, 49)$ ).
Since $25 \ge k_{\text{up}}$ , the leaf containing $25^*$ is the leftmost child of $B_2 = (33, 44)$ . The smallest key value in $B_2$ is $33$ .

Final answer

Common trap

Assuming $k_{\text{up}}$ (23 or 25) remains inside the right split of internal node $B$ instead of being pushed up to parent $A$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 57 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source