GATE CS 2025 Set 2 Q47 — File Organization and Indexing (B and B+ Trees)

To insert the key $23$, we first traverse the $\text{B}^+$-tree along the given path:

• From root $\mathrm{A} = (49, 77, 83, -)$, since $23 < 49$, we follow the first pointer to node $\mathrm{B}$.
• From $\mathrm{B} = (7, 19, 33, 44)$, since $19 \le 23 < 33$, we follow the pointer between $19$ and $33$ to leaf node $\mathrm{C} = (20^*, 22^*, 25^*, 26^*)$.

Since leaf $\mathrm{C}$ is full (maximum capacity of 4 keys), inserting $23$ causes a split of the keys $\{20, 22, 23, 25, 26\}$. Depending on the split policy, we have two standard cases:

Case 1: Left-biased split (2 keys left, 3 keys right)

• Left leaf: $\mathrm{C}_1 = (20^*, 22^*)$
• Right leaf: $\mathrm{C}_2 = (23^*, 25^*, 26^*)$
• The smallest key in the right leaf, $23$, is copied up to parent $\mathrm{B}$.

Case 2: Right-biased split (3 keys left, 2 keys right)

• Left leaf: $\mathrm{C}_1 = (20^*, 22^*, 23^*)$
• Right leaf: $\mathrm{C}_2 = (25^*, 26^*)$
• The smallest key in the right leaf, $25$, is copied up to parent $\mathrm{B}$.

In both cases, the leaf containing $25^*$ is $\mathrm{C}_2$, and the key copied up to the parent $\mathrm{B}$ is $K_{\text{up}} \in \{23, 25\}$.

Now, parent $\mathrm{B} = (7, 19, 33, 44)$ is also full. Inserting $K_{\text{up}}$ into $\mathrm{B}$ results in the key set $\{7, 19, K_{\text{up}}, 33, 44\}$, causing $\mathrm{B}$ to split:

• The middle key $K_{\text{up}}$ is pushed up to root $\mathrm{A}$.
• $\mathrm{B}$ splits into left node $\mathrm{B}_1 = (7, 19)$ and right node $\mathrm{B}_2 = (33, 44)$.

The right leaf $\mathrm{C}_2$ (containing $25^*$) is pointed to by the leftmost child pointer of the newly created right internal node $\mathrm{B}_2 = (33, 44)$. Thus, the parent of the leaf containing $25^*$ is $\mathrm{B}_2$.

The smallest key value in $\mathrm{B}_2$ is 33.