GATE CS 2008 Q41 — File Organization and Indexing (B and B+ Trees)

For a B-tree of order $p = 4$:

• The maximum number of keys in any node is $p - 1 = 3$.
• A node splits when it receives a $4^{\text{th}}$ key.

Let $L$ be the number of leaf splits and $I$ be the number of internal node splits. The total number of splits is $S = L + I$.

1. Maximum Leaf Splits ($L$):

• The first leaf split requires $4$ insertions.
• Each subsequent leaf split requires at least $2$ additional insertions (since a split leaf contains at least $1$ key, and we must insert $2$ more keys to make it $4$).
• For $L$ leaf splits, the minimum number of insertions required is: $$\text{Insertions} \ge 4 + 2(L - 1) = 2L + 2$$
• With $10$ insertions: $2L + 2 \le 10 \implies L \le 4$.

2. Maximum Internal Splits ($I$):

• Each leaf split promotes exactly $1$ key to the internal level. Thus, the total number of keys in all internal nodes is at most $L = 4$.
• To split an internal node, it must accumulate $4$ keys. With at most $4$ keys in total across all internal nodes, we can have at most $I = 1$ internal split (as a split distributes these $4$ keys across $3$ internal nodes, preventing any single node from reaching $4$ keys again).

Thus, the maximum number of node splits is $L + I = 4 + 1 = 5$.