GATE 2025 CS (CS2) – Question 57
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
- GATE 2024 CS (CS1) Q21
- GATE 2024 CS (CS2) Q26
- GATE 2023 CS Q62
- GATE 2021 CS (CS1) Q57
- GATE 2020 CS Q64
- GATE 2019 CS Q24
All File Organization and Indexing (B and B+ Trees) questions →