GATE CSE 2015 Set 2 | Question: 6

Question

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 ______.

Comments

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.

PS:

@Anu007 ji, Please check 

http://2.bp.blogspot.com/--7OpPitZhoQ/Uy8TVPCxenI/AAAAAAAACPs/lUkMHUTlM2g/s1600/Structure+of+a+leaf+node+of+B++tree.jpg

---

no it is bidirectional.

see each node has  |p_left| key |p| key|p_right|

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.

Answer 1

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

Comments

Same doubt… Why is it saying order 1 but have 3 pointers

---

Hey, I am not sure I understand what you are saying. Do you mean to say that 1 order here means there is one middle pointer per block. ie, do you mean that when telling the order of a B-tree we exclude the first and last? 

---

@phaniphani now i got it what u were trying to say yes ig this is mistake here 

Answer 2

The total number of nodes accessed including root will be 5.

The order is,

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

Comments

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

Answer 3

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 amarVashishth sir's answer for clarity.