search
Log In
30 votes
5.1k views

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
edited by
5.1k views
2
@Arjun Sir ... typo ... its a b+tree of order 3
1
It is order 1 in the paper :O
1
So marks to all ???
1
Tree of order m has m-1 keys. Given order is 1 => 0 keys? :O
1

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

1
root has atleast 2 block pointers atmost p pointers
0

@amarVashishth But no conclusion yet?

3

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

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

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 

0

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.

0

@Chhotu  By default it is unidirectional.

3 Answers

53 votes
 
Best answer

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


edited by
3
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.
6
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
0
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"
2
If asked less than or equal to 15 then also #5 nodes to be fetched??because as we reach 15 terminate to search??
0
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)
0
@ Vicky rix sir this is B+ tree not B-tree .you are actually defining the property of B-tree
0
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.
0
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.
18 votes
The total number of nodes accessed including root will be 5.

The order is,

(9)-->(5)-->(5,7)-->(9,11)-->(13,15).
0
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
1 vote

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

53 votes
8 answers
1
5k views
A Young tableau is a $2D$ array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with $\infty$, and hence there cannot be any entry to the right of, or below a $\infty$. The following Young tableau consists of unique ... $1$) to be shifted, to remove $1$ from the given Young tableau is _____.
asked Feb 12, 2015 in DS jothee 5k views
39 votes
4 answers
2
7k views
Consider a B+ tree in which the search key is $12$ $\text{byte}$ long, block size is $1024$ $\text{byte}$, recorder pointer is $10$ $\text{byte}$ long and the block pointer is $8$ $\text{byte}$ long. The maximum number of keys that can be accommodated in each non-leaf node of the tree is ______.
asked Feb 16, 2015 in Databases jothee 7k views
29 votes
4 answers
3
3.4k views
Let $X$ and $Y$ denote the sets containing 2 and 20 distinct objects respectively and $F$ denote the set of all possible functions defined from $X$ to $Y$. Let $f$ be randomly chosen from $F$. The probability of $f$ being one-to-one is ______.
asked Feb 13, 2015 in Set Theory & Algebra jothee 3.4k views
27 votes
5 answers
4
4.6k views
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
asked Feb 13, 2015 in Theory of Computation jothee 4.6k views
...