GATE CS 2019 Q14 — File Organization and Indexing (B and B+ Trees)

A $B^+$ tree is a self-balancing search tree optimized for systems that read and write large blocks of data. Let's analyze each statement to identify the incorrect one:

• Option A: $B^+$ trees are designed to be perfectly height-balanced, meaning all leaf nodes are at the exact same depth. This ensures $O(\log n)$ search, insertion, and deletion times. Thus, this statement is correct.
• Option B: In a $B^+$ tree, non-leaf (internal) nodes only store search keys and pointers to child nodes to guide the search. They do not store pointers to the actual data records. Data record pointers (or the data records themselves) are stored exclusively in the leaf nodes. (This is a key difference between B-trees and $B^+$ trees). Thus, this statement is incorrect.
• Option C: Within any node of a $B^+$ tree, the keys are kept in sorted order to allow efficient searching (such as binary search) within the node. Thus, this statement is correct.
• Option D: Leaf nodes in a $B^+$ tree are linked together in a linked list (each leaf has a pointer to the next leaf). This allows highly efficient sequential scans and range queries. Thus, this statement is correct.

Therefore, the statement that is NOT correct is B.