GATE IT 2006 | Question: 61

Question

In a database file structure, the search key field is $9$ $bytes$ long, the block size is $512$ $bytes$, a record pointer is $7$ $bytes$ and a block pointer is $6$ $bytes$. The largest possible order of a non-leaf node in a$ B+$ tree implementing this file structure is

• A. $23$
• B. $24$
• C. $34$
• D. $44$

Answer 1

Answer is (C).

From the structure of $B+$ tree we can get this equation:

$n\times p + (n-1)\times k \leq B$ ( for non leaf node)

Here, n=order, p=tree/block/index pointer,  B=size of block

I non leaf node no record pointer is there in B+ tree.

So, $n\times p + (n-1)k \leq B$

$n\times 6 + (n-1)\times 9 \leq 512$

$\implies n \leq 34.77$

Largest possible value for $n$ is $34.$

Comments

So, still max number of key values at the leaf node and order of internal nodes don’t have any relationship. I mean they need not be equal always. If the order is equal to 34 for internal node then the max number of search key values can be greater than or equal to 34. Please correct me if I am wrong. @adad20 @ayush.5.

---

@ankit3009 Yes in B+ trees order of leaf and order of internal nodes are different. In internal node order defines max number of children it can have while in leaf order means max #key and record pointer pairs it can have.

---

Thanks @adad20 and @ayush.5 :)

Answer 2

option C

Because in non leaf node of the B+ tree there is not any record pointer 

so formula will be  n*p + (n-1)*(k) <= B ( for non leaf node) 

put the values and get the answer k=9 and  p=6 and B=512 

so answer is 34

Answer 3

option B) 24

Comments

how plz explain

---

this is correct answer in the case of they are asking for leaf but they are asking for non-leaf so 24 is wrong