What will be the answer for this ,

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

The Gateway to Computer Science Excellence

+38 votes

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

+58 votes

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

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

@ Sachin Mittal , @ Sushant Gokhale

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?

+1

In a B+ tree, there are no record pointers in non-leaf nodes. Hence, the 10bytes of record pointers are not considered.

+6 votes

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**

+2 votes

Maximum keys =50 (answer)

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.

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 ?

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

@ Utsav09

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

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

52,345 questions

60,503 answers

201,892 comments

95,332 users