edited by
13,189 views
44 votes
44 votes

With reference to the B+ tree index of order $1$ 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 ______.

edited by

3 Answers

Best answer
68 votes
68 votes

whichever way you go from the root to leaves, you'll always end up counting $5$ nodes.

edited by
21 votes
21 votes
The total number of nodes accessed including root will be 5.

The order is,

(9)-->(5)-->(5,7)-->(9,11)-->(13,15).
4 votes
4 votes

The question wants us to perform a range query from 7 to 14 (both inclusive) on a $B^+ \ tree$

This requires for us to first reach the leaf node that has 7, and then traverse in a forward direction until we reach 14. Or vice versa.

This works because:-

  1. ALL the keys can be found in the leafs of a $B^+ \ tree$ — which are interconnected.
  2. Keys are arranged in sorted order. Hence, just finding one end of the range is enough.

 

So, we need 3 accesses (counting root) to reach the leaf that has one end of the range. Then 2 more accesses to reach the other end.

So, 5


Refer to the pictures in sir's answer for clarity.

edited by
Answer:

Related questions

51 votes
51 votes
4 answers
2