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

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

+52 votes

+5

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?

0

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

+5 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)]..???????????**

0 votes

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,505 answers

195,555 comments

101,051 users