The Gateway to Computer Science Excellence
+28 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 ______.

in Databases by Veteran (105k points)
edited by | 3.8k views
@Arjun Sir ... typo ... its a b+tree of order 3
It is order 1 in the paper :O
So marks to all ???
Tree of order m has m-1 keys. Given order is 1 => 0 keys? :O

@monanshi you should read above comments too, they had the same issue.

root has atleast 2 block pointers atmost p pointers

@amarVashishth But no conclusion yet?


it is self understood that what should be correction to that, also order does not matter here.

Please update the question. It should be of order=3 or else the solution doesn't make sense

Notice --> In this question next block pointers in leaf node are bi-directional. But I think in general next block pointers in leaf node are unidirectional.


@Anu007 ji, Please check 


no it is bidirectional.

see each node has  |pleft| key |p| key|pright|

so pleft of one node contain address of its left node

while pright of left node contain address of its left node.


@Chhotu  By default it is unidirectional.

3 Answers

+50 votes
Best answer

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

by Boss (30.8k points)
edited by
Wouldn't the next node (17,null) be checked to ascertain the value of the first search key (referring to the diagram with green highlight) ? Otherwise, how will the program know when to stop accessing nodes in the backing store to retrieve the values?

Edit - I understand why it's the case - they've asked for range query with search key greater than or equal to 7 and less than 15. Thus after accessing the node containing 15, it won't check further as the range upper bound has been encountered. Thus only 5 blocks will be accessed.
The question clearly mentions "Records with search key greater than or equal to 7 and less than 15". So, when we are traversing it is safe to stop as soon as we reach search key 15. However, if he asked less than or equal to 15, then we must check the next node
To satisfy the query we should not only fetch the index blocks but after that we need to also fetch the data blocks .. since "minimum number of blocks that needs to be fetched" is asked ... we can think that all index records are having the record pointer as pointing to the same node .. in that case 5 index blocks + 1 data block = 6 blocks are needed ...
this is what i feel .. i think in the question they should have mentioned "how many index blocks are to be fetched to execute this query"
If asked less than or equal to 15 then also #5 nodes to be fetched??because as we reach 15 terminate to search??
Here in the secound case why internal node 5 is not accessed and in the leaf level what is significance of two direction arrow(is it is doubly linked list)
@ Vicky rix sir this is B+ tree not B-tree .you are actually defining the property of B-tree
I am thinking which path would be traversed in actual scenario. Why green path would be traversed?

As we know that $B^+$ tree support range queries, so whatever nodes being accessing will be compared with the range given that is $(\geq7  \text{ and}  \lt15)$. Due to this only pink path would be traversed not the green path.
The question asks the number of nodes fetched, as in a B+ tree data lies only in the leaf why would internal nodes be fetched?. The question is not asking about accessed. According to this 3 nodes should be fetched.
+17 votes
The total number of nodes accessed including root will be 5.

The order is,

by Boss (19.9k points)
I am also not getting why in the leaf nodes doubly linked nodes are used here.  Leaf nodes in b plus tree  store record pointer as well as block pointer is that they wanna to represent by doubly linked list
0 votes

In B+ trees data pointers are present only in the leafs. So concern yourself with the leaf nodes that contain data pointers to keys from 7 to 15 (both inclusive)

There are three such leaf nodes, and to reach them e come down two levels. So however you do it, you'll always end up traversing 5 nodes.

by Loyal (6.2k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,258 answers
104,735 users