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

there is no type or nothing wrong here
order mean doesnot always that max number of total pointers in b+ tree
here what if order p means p+1 keys  or maybe some author dependent ,i guess professor only took half question from somewhere where subparts may needed order value
but in our question it is not needed
and bidirection shows a special case in b+tree
b tree can have many cases and this is one of them
try to find things from given tree thats the rules

---

for this question those who have doubt regarding the order of tree, If you check few old pYQ you will find that order and degree  are often used interchangebly.

for a b+tree of order d the key values ranges from d to 2d.

 

---

What does the accepted answer to this question mean when written as "...whichever way you go from root to leaves..." ? Given the query "Get all records with a search key greater than or equal to 7 and less than 15", do we even have this discretion to visit a node which is greater than 9 ?

 

Answer 1

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

Comments

As far as i remeber, the data is stored in the leaves itself in B+ TRees? no?

---

yeah

---

@phaniphani A different definition of order is being used here . It is referring to the minimum number of keys a node can hold and not the maximum number of child pointers.

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.

Answer 4

we are given with a B+ tree in which the key and data pointers are present along with a single block pointer at each leaf node.

we need to get some records,

we can start from left or start from right.

if start from left, 5 nodes need to be fetched similar for the right as well.

as it is bidirectionally, normally it isn't

so answer 5.