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

edited | 6.2k views

$(n-1)12 + n*8<=1024$

$n<=51$

In non leaf node number of keys $= n-1$

$= 51-1=50$
by
edited
+8

What will be the answer for this ,

The maximum number of keys that can be accommodated in each leaf node of the tree is ______.

+20
Let n be orfer of leaf node

12n+10n+8<=1024

n=46
0
Thank you
0

in non leaf node number of keys = n-1 if suppose this the formula, then

https://gateoverflow.in/3605/gate2006-it_61 even in this question they are asking non-leaf node but we are not using this n-1 here?

+3

@ Prasanna we have done (n-1)  here because here in this que no of keys accomodated in each non leaf node is asked.

But here https://gateoverflow.in/3605/gate2006-it_61 order is asked.

0

But then space for a leaf node is:

12*50 + 10*50 + 8 = 1108 which is greater than the block size. Shouldn't we be considering this fact too?

Shouldn't we calculate the max allowed value for both leaf node and internal node and then take the minimum of them?

0
What role does record pointer have ? and any sources for this formula ?
0
Why aren't you using record pointer value?? then answer would be 34.
0
@Pooja Palod I am also getting 46, is this the answer ?
0

maximum number of keys:most important

+1
In a B+ tree, there are no record pointers in non-leaf nodes. Hence, the 10bytes of record pointers are not considered.
0
So maximum number of Block pointers = 51 and

Maximum number of Keys in the internal node = 51-1 =50.
+1

For leaf nodes it is-

n*(K+RP)+BP <= Block size

and for non-leaf nodes it is-

n*BP+(n-1)K <= Block size

this is the correct way to solve

here for non leaf node order is max no of keys/node

means max keys/node=p and (Bp)block_ptr/node=p+1

(p+1)(Bp size)+p(key size)<=block size

(p+1)(8)+p(12)<=1024

20p<=1016

p<=50.8

p=50

0
@rajoramanoj  I believe this is the correct way to solve this. I don't know why people are calculating 51 and then subtracting 1 to get 50.
0

Non leaf node order is maximum number of children it can have

maximum number of keys in non leaf = 50

order = 51

Please correct me if i am wrong.

because keys are always 1 less than block pointer in non-leaf node. Here record pointer is given just for confusion as record pointer dont even exist in non-leaf. Only leaf node contains record pointer.
+1
true. In B+ tree only leaf nodes have record pointers.

BTW, what would be the value if the node was a leaf node ?
0
non leaf node has only block pointers, so we have ignored the value of record pointer ? am I correct ?
+1

yes...for non-leaf node we would consider only block pointer i.e(n+1)....but in the case of leaf node [n keys,n record pointer(data pointer),1 block pointer(sibling pointer)]..???????????

+1 vote
P (BLOCK POINTER) + (P-1) SEARCH KEY

P8+(P-1)12 <=1024

P8+12P-12<=1024

P8+12P<=1024+12

20P<=1036

P=51.8

P=51

AND DUE TO NON LEAF (P-1)

51-1=50 SO 50 WILL BE CORRECT ONE

#Cross_check

20*51.8=1024 and given block size is 1024 it is correct

why we dont take 52 even if it is mention in the option just because if we put in the equation 1040-12=1028 and 1028 is greater than BLOCK SIZE ..

edited