GATE CSE 2007 | Question: 63, ISRO2016-59

Question

The order of a leaf node in a $B^+$ - tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is $1K\;\text{bytes}$, data record pointer is $7\;\text{bytes}$ long, the value field is $9\;\text{bytes}$ long and a block pointer is $6 \;\text{bytes}$ long, what is the order of the leaf node?

• A. $63$
• B. $64$
• C. $67$
• D. $68$

Comments

For a leaf node of B+ tree :
 
Bp  +  (m-1) * (Rp + key) <= BlockSize

m is order of B+ tree
Note : There is just one block pointer in every leaf node of a B+ tree.
So, according to given values :
           6 +  (m-1) * (9+7)  <=  1024
           6 + 16m - 16  <=  1024
           16m  <=  1034
           m  <=  64.62
           m  =  64

It's my answer, i'm still trying to figure it out how the answer is 63.
plzz, let me know where i did mistake.

---

Refer: Fundamental of Database System, 6th Ed, Navathe, Page 654

 

---

@Viltu+Jujhajiya you are using the default definition of order.

In the question we are already given what is order in B+ Tree.

Correct equation will be $BP+(9+7)*k \leq1024$ , where $k$ is order of B+ Tree.

Answer 1

63 is correct order of leaf node .

so ans is (A) 63

Answer 2

Answer: 64

 Explanation:  Let the order of leaf node is n. As per given,

Block size =1K =1024 =

6+7n+(n-1 )9 =1024

16n =1024  

n=64

 

It is a correct ?