With reference to the B+ tree index of order 3 shown below, the minimum number…
2015
With reference to the B+ tree index of order 3 shown below, the minimum number of nodes (including the Root node) that must be fetched in order to satisfy the following query: "Get all records with a search key greater than or equal to 7 and less than 15" is ____________.
Attempted by 162 students.
Show answer & explanation
Correct answer: 5
Key idea: start at the root, follow internal pointers to the leaf that contains the first qualifying key (7), then scan leaf nodes using sibling pointers until keys reach 15 (exclusive).
Fetch the root node (contains key 9) to decide which child to follow.
Fetch the appropriate internal node on the left (contains key 5) to reach the leaf containing 7.
Fetch the leaf node that contains 7 (the leaf with [5,7]).
Scan to the next leaf using the leaf sibling pointer and fetch the leaf with [9,11].
Scan to the next leaf and fetch the leaf with [13,15]. We stop after this leaf because 15 is excluded (range is < 15).
Count of fetched nodes: root (1) + one internal node (1) + three leaf nodes (3) = 5.
A video solution is available for this question — log in and enroll to watch it.