GATE CS 2010 Q18 — File Organization and Indexing (B and B+ Trees)

To find the minimum number of keys in any non-root node of a $B^+$-tree, we must consider both non-root internal (non-leaf) nodes and leaf nodes.

Given that the maximum number of keys in any node is $U = 5$.

1. Non-root Internal Nodes

• The maximum number of pointers (children) an internal node can have is $P = U + 1 = 5 + 1 = 6$.
• The minimum number of pointers for a non-root internal node is $\lceil P/2 \rceil = \lceil 6/2 \rceil = 3$.
• Since the number of keys in an internal node is always $\text{pointers} - 1$, the minimum number of keys in a non-root internal node is: $$\text{Min keys (internal)} = 3 - 1 = 2$$

2. Leaf Nodes

• The minimum number of keys in a leaf node is $\lceil U/2 \rceil = \lceil 5/2 \rceil = 3$.

Comparing both cases, the minimum number of keys in any non-root node is $\min(2, 3) = 2$.

Therefore, the correct option is B.