GATE CS 2005 Q28 — File Organization and Indexing (B and B+ Trees)

The correct option is D.

Explanation:

Database relations are stored on secondary storage devices (such as magnetic disks or SSDs), where data transfer between the disk and main memory is performed in fixed-size units called blocks (or pages).

• Binary Search Trees (BSTs): A BST has a maximum fan-out of 2. For a relation with $N$ records, the height of a balanced BST is $O(\log_2 N)$. Since each node access potentially requires a separate disk I/O, searching in a BST is highly inefficient.
• $B^+$-trees: These are multi-way search trees designed specifically for disk storage. The size of a $B^+$-tree node is typically made equal to the disk block size. This allows each node to store a large number of keys (high fan-out, e.g., $d \ge 100$). Consequently, the height of the tree is reduced to $O(\log_d N)$, requiring only $3$ to $4$ disk I/O operations even for millions of records.

Thus, because data transfer from disks is in blocks, $B^+$-trees are highly preferred over binary search trees for indexing database relations.