GATE CS 2019 Q.24 (CS Q.14): File Organization, B-Trees and B+ Trees Indexing

Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table?

B+ Tree is a height-balanced tree

Non-leaf nodes have pointers to data records

Key values in each node are kept in sorted order

Each leaf node has a pointer to the next leaf node

Official answer and solution

Solution

Review the architectural definitions of B+ tree internal versus leaf nodes.

Let us check the statements regarding B+ trees:

Option A: A B+ tree is balanced because all leaf nodes appear at the exact same depth from the root. This statement is correct.
Option B: In a B+ tree, data records (or pointers to data records) are stored exclusively in the leaf nodes. Non-leaf (internal) nodes store only routing search keys and tree node pointers to guide traversal; they do NOT store pointers to data records. Hence, statement B is NOT correct.
Option C: Keys within each node are stored in strictly sorted ascending order. This statement is correct.
Option D: Leaf nodes are linked together as a singly (or doubly) linked list via pointers to facilitate efficient sequential and range queries. This statement is correct.

Final answer

Common trap

Confusing a B tree with a B+ tree (B trees store data pointers in internal nodes as well, whereas B+ trees store data pointers only in leaf nodes).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.