GATE CS 2016 Set 2 Q21 — File Organization and Indexing (B and B+ Trees)

By definition, a B+ Tree is a self-balancing search tree where all leaf nodes are kept at the exact same level (depth).

Let's analyze the options:

• Option A: Since all leaf nodes reside at the same bottom-most level, the length of the path from the root to any leaf node is identical. This is the precise definition of balance in B/B+ trees. Thus, this option is correct.
• Option B: This describes height-balanced trees like AVL trees (where the heights of left and right subtrees differ by at most $1$). For B+ trees, the path length difference between any two leaves is strictly $0$, not $1$.
• Option C: The number of children of non-leaf nodes is determined by the order of the tree ($d$) and must be between $\lceil d/2 \rceil$ and $d$. Sibling nodes can have any number of children within this range; they do not need to differ by at most $1$.
• Option D: The number of records/keys in leaf nodes depends on the fill factor and capacity, and can vary widely between $\lceil (d-1)/2 \rceil$ and $d-1$. They do not need to differ by at most $1$.

Therefore, B+ trees are balanced because the lengths of the paths from the root to all leaf nodes are all equal.