The GATE Grind

GATE 2025 CS (CS2) – Question 57

Databases · File Organization and Indexing (B and B+ Trees) · 2 marks · Numerical answer

In a B$^+$-tree where each node can hold at most four key values, a root to leaf path consists of the following nodes:

A = (49, 77, 83, -), B = (7, 19, 33, 44), C = (20*, 22*, 25*, 26*)

The *-marked keys signify that these are data entries in a leaf.

Assume that a pointer between keys $k_1$ and $k_2$ points to a subtree containing keys in $[k_1, k_2)$, and that when a leaf is created, the smallest key in it is copied up into its parent.

A record with key value 23 is inserted into the B$^+$-tree.

The smallest key value in the parent of the leaf that contains 25* is __________. (Answer in integer)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 33

Explanation

Max 4 keys per node. Leaf C holds 20*, 22*, 25*, 26* (full). Insert 23.

**Leaf split.** The leaf would hold 5 keys: 20, 22, 23, 25, 26. Split it, and **copy up** the smallest key of the new right leaf. With the split $(20,22\mid23,25,26)$ the new leaf is $(23^*,25^*,26^*)$, and 23 is copied up.

**Parent B overflows.** B is $(7,19,33,44)$; adding 23 gives $(7,19,23,33,44)$ with 5 keys. Split the internal node: $(7,19)$ and $(33,44)$, and move 23 up to the parent A (internal keys move up, they are not copied).

**Where is 25\*?** A pointer between keys $k_1$ and $k_2$ points to keys in $[k_1,k_2)$. After the split, the leaf with 23, 25, 26 lies in $[23,33)$, which is the first (leftmost) child of the new node $(33,44)$.

So the parent of the leaf that contains 25\* is $(33,44)$, and its smallest key is **33**.

More File Organization and Indexing (B and B+ Trees) questions

All File Organization and Indexing (B and B+ Trees) questions →