GATE CS 2016 Set 2 Q.31 (CS Q.21): File Organization, B-Trees and B+ Trees Indexing

B+ Trees are considered BALANCED because

the lengths of the paths from the root to all leaf nodes are all equal.

the lengths of the paths from the root to all leaf nodes differ from each other by at most 1.

the number of children of any two non-leaf sibling nodes differ by at most 1.

the number of records in any two leaf nodes differ by at most 1.

Official answer and solution

Official answer: A
From: Official GATE 2016 answer key

Solution

Recall the structural invariant that defines the balance of a B+ tree.

A B+ tree is a self-balancing search tree data structure widely used in databases and file systems.

In a B+ tree:

All data records (or pointers to data records) are stored in the leaf nodes.
Internal nodes store only index keys and child pointers to direct searches.
Every leaf node appears at the exact same depth from the root.

Consequently, the length of the path from the root to every leaf node is identical. This uniform height ensures predictable $O(\log n)$ search, insert, and delete operations and forms the formal definition of balance in B and B+ trees.

Therefore, option (A) is correct.

Final answer

Common trap

Confusing the B+ tree definition of balance (all leaves at the same depth) with AVL tree height-balance (heights of left and right subtrees differ by at most 1).

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

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 31 of 65, printed as CS Q.21
Section: Computer Science and Information Technology

Report an error in this question

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

Question

Solution

Source