GATE CSE 2015 | Set 3 | Question: 46

Question

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

Comments

All questions related to order{leaf, internal}, number of keys in B+ tree 

Databases: GATE CSE 2002 | Question: 2.23, UGCNET-June2012-II: 26

Databases: GATE CSE 2004 | Question: 52

Databases: GATE CSE 2007 | Question: 63, ISRO2016-59

Databases: GATE CSE 2010 | Question: 18

Databases: GATE CSE 2015 Set 3 | Question: 46

Databases: GATE CSE 2017 Set 2 | Question: 49

Databases: GATE IT 2006 | Question: 61

Answer 1

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$

Comments

And how different is disk block from a memory block? @abir_banerjee

---

@Abhrajyoti0 disk block means secondary storage device not main m/y .

---

while calculating i forgot that the non leaf node doesn't contain the record pointers in the B+tree !

Answer 2

 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

Comments

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

---

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.

---

They are finding the order of the tree first and then calculating max no. of keys based on it.
Like Number of keys = Order-1
Here in rajoramanoj’s answer, he’s finding the max number of keys directly instead of finding order.

Answer 3

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.

Comments

true. In B+ tree only leaf nodes have record pointers.

BTW, what would be the value if the node was a leaf node ?

---

non leaf node has only block pointers, so we have ignored the value of record pointer ? am I correct ?

---

@ 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)]..???????????

Answer 4

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

Answer 5

Search key size = 12B

Block Size = 1024B

Block Pointer = 8B

Record Pointer = 10B (not required to solve this question)

Wrt Internal node if order is y then

Maximum keys possible are y-1

Maximum block pointer possible= y

There is no record pointer in internal node

So,

y(8)+(y-1)(12)<=1024

y<=51.9

y=51

So y-1= 50 is maximum number of keys possible

ANSWER 50