GATE CS 2003 Q65 — File Organization and Indexing (B and B+ Trees)

In a 2-3-4 tree (a B-tree of order 4), insertion is performed using a top-down approach. As we search for the insertion location from the root to the leaf, any 4-node (a node containing 3 keys) encountered along the path is split immediately. This proactive splitting ensures that we never have to propagate splits back up the tree.

Let's trace the insertion of key $G$ step-by-step:

1. Identify the path: We start at the root $[M]$. Since $G < M$, we must descend to its left child, which is the 4-node $[D, H, L]$.
2. Split the 4-node $[D, H, L]$:
   • The middle key $H$ is promoted to the root, changing the root to $[H, M]$.
   • The remaining keys split into two 2-nodes: $[D]$ and $[L]$.
   • The children are distributed: $[D]$ gets $[B, C]$ and $[E, F]$, while $[L]$ gets $[J, K]$ and $[N, O]$.
3. Descend and Insert:
   • From the new root $[H, M]$, since $G < H$, we move to the left child $[D]$.
   • Since $G > D$, we descend to the right child of $[D]$, which is the leaf node $[E, F]$.
   • Since $[E, F]$ is not a 4-node, we insert $G$ directly into it, resulting in $[E, F, G]$.

The right child of the root, $[P, T, X]$, is not visited during this insertion, so it remains unsplit. This resulting structure corresponds exactly to Option B.