Question

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?

• A. B$^+$ tree is a height-balanced tree
• B. Non-leaf nodes have pointers to data records
• C. Key values in each node are kept in sorted order
• D. Each leaf node has a pointer to the next leaf node

Hint:

Key difference to remember: {B-tree} may store data pointers in internal nodes, but {B$^+$ tree} stores all data pointers {only at leaf nodes}.

Answer 1

The Correct Option is B

The question asks which statement is NOT correct about the B⁺ tree data structure used for creating an index in a relational database table. Let's analyze each option:

1. B⁺ tree is a height-balanced tree:
   • A B⁺ tree is indeed a height-balanced tree, meaning that all leaf nodes are at the same level. This property ensures that the time complexity of operations like search, insert, and delete is logarithmic.
2. Non-leaf nodes have pointers to data records:
   • This statement is incorrect. In a B⁺ tree, non-leaf nodes do not store pointers to data records; instead, they store pointers to the child nodes. Only the leaf nodes contain pointers (or references) to the actual data records. This is what differentiates a B⁺ tree from other tree structures.
3. Key values in each node are kept in sorted order:
   • This is a correct characteristic of B⁺ trees. Each node maintains its key values in a sorted order to facilitate efficient search operations.
4. Each leaf node has a pointer to the next leaf node:
   • This is correct. B⁺ trees have a linked list-like structure between the leaf nodes, which makes range queries more efficient.

Consequently, the statement "Non-leaf nodes have pointers to data records" is NOT correct regarding the B⁺ tree structure.