GATE CS 2025 Set 1 Q.21: File Organization, B-Trees and B+ Trees Indexing

Consider the following $B^+$ tree with 5 nodes, in which a node can store at most 3 key values. The value $23$ is now inserted in the $B^+$ tree. Which of the following options(s) is/are CORRECT?

A B+ tree of height 1 with 5 nodes where each node holds up to 3 keys. The root node contains keys [6, 12, 19] and points to four leaf nodes: [1, 4, 3], [7, 9, 10], [13, 15, 17], and [20, 21, 22].

None of the nodes will split.

At least one node will split and redistribute.

The total number of nodes will remain same.

The height of the tree will increase.

Official answer and solution

Official answer: B and D
From: Official GATE 2025 answer key

Note on this question

In the official paper diagram, the leftmost leaf shows keys [1, 4, 3]; this does not affect inserting 23 into the rightmost leaf [20, 21, 22].

Solution

Trace the insertion of key 23 into the rightmost leaf node [20, 21, 22] and propagate the split to the root node [6, 12, 19].

Searching for $23$ in the root $[6, 12, 19]$ follows the rightmost pointer ( $23 > 19$ ) to the leaf node $[20, 21, 22]$ .
Because a node can store at most $3$ keys, inserting $23$ into $[20, 21, 22]$ causes the leaf node to overflow ( $4$ keys: $20, 21, 22, 23$ ) and split into two leaf nodes.
The separator key from the leaf split is pushed up to the parent (root) node $[6, 12, 19]$ . Since the root also already contains the maximum of $3$ keys, the root node also overflows and splits, creating a new root node one level higher.

Therefore, at least one node will split and redistribute (B) and the height of the tree will increase (D).

Final answer

Options (B), (D)

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

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 21 of 65
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