edited by
21,248 views
51 votes
51 votes
Consider a B+ tree in which the search key is $12$ $\text{bytes}$ long, block size is $1024$ $\text{bytes}$, record pointer is $10$ $\text{bytes}$ long and the block pointer is $8$ $\text{bytes}$ long. The maximum number of keys that can be accommodated in each non-leaf node of the tree is ______.
edited by

4 Answers

Best answer
75 votes
75 votes
In a B+ tree of order $n$, for a non-leaf node we can have up to $(n-1)$ keys and $n$ child pointers (pointing to child blocks).

$\therefore (n-1)12 + n\times 8\leq 1024$

$\implies n\leq 51$

Number of keys $= n-1$

$= 51-1=50$
edited by
8 votes
8 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
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.
1 votes
1 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 ..
edited by
Answer:

Related questions