GATE CS 1999 Q1.25 — File Organization and Indexing (B and B+ Trees)

The correct option is B.

Explanation:

• Option A is incorrect: Both B-trees and B⁺ trees are designed for disk-based storage to minimize disk I/O operations. They are not distinguished by disk vs. main memory usage.
• Option B is correct: In a B⁺ tree, all keys and data pointers are stored in the leaf nodes, and these leaf nodes are linked together sequentially (usually as a doubly linked list). To perform a range query, we only need to find the starting key using the tree structure and then traverse the leaf nodes sequentially. In a standard B-tree, keys are distributed across all levels, requiring a costly in-order traversal (moving up and down the tree) which results in many random disk accesses.
• Option C is incorrect: Both B-trees and B⁺ trees can be used to implement both primary and secondary indexes.
• Option D is incorrect: The height of a B⁺ tree is logarithmic with respect to the number of records $N$, i.e., $H \approx \log_{B} N$ (where $B$ is the fan-out/order of the node). Thus, the height directly depends on the number of records.