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

same doubtt!!!

---

GATE CSE 2007 - Take a look; it could be helpful.

---

Question me already diya hai ki order of leaf node voh hoga jo ki no. Of key  value store hogi node me p=64 i.e maximum key 63 i.e order 63

Answer 1

The answer is option A.

$B_{p} + P(R_{p} + \text{Key} ) \leq \text{BlockSize}$

$\implies 1\times 6 + n(7 + 9) \leq 1024$

$\implies n \leq$ $63.625$.

So, $63$ is the answer.

Comments

In leaf node of B+ tree we have only one block pointer . That point to block in right side for range access .

---

Yes, they have explicitly asked for an order of leaf node, at leaf node each node has a single block pointer that points to its adjacent block. Further, read line 1st, they have defined the structure of the leaf node of B+ tree themselves and we need to follow that so that's why we are considering both value and data record pointer.

---

thanks

Answer 2

For leaf nodes order is-

n*(K+RP)+BP <= Block size

and for non-leaf nodes order is-

n*BP+(n-1)K <= Block size

Here question is about Leaf nodes so it would be

n*(K+RP)+BP <= Block size

Therefore, n*(9+7)+6 <= 1024

                  16n<=1018

                    n <= 63.6

So, n is 63. Hence option A is correct.

 

Comments

when to consider ceil and when to consider floor

 

---

@manas,  Let A and B are integers only.

Case 1: If A <= B, on solving you got A is 63.6 - then you need to take floor. Otherwise LHS is not less than RHS.

Case 2: If A >= B, on solving you got A is 63.6 - then you need to take ceil. Otherwise LHS is not grater than RHS.

 

Understand the logic behind that:

we solve the equation with '=' and get 63.6

Then try to put the floor and ceil values in the original equation,  then we can get to know.

---

Thanks

Answer 3

For tree of order p, leaf nodes can have max p-1 keys. Hence

$(p-1)(DP + V) + BP <= Block_Size$

(p-1)16 + 6 <= 1024

p = 64

Reference: https://en.wikipedia.org/wiki/B%2B_tree#Overview

Comments

but here question specifies order is maximum number of keys.

---

I accept its an incorrect answer in the context of this question (since order of leaf node is asked). If order of B tree was asked, this would be the correct solution.

---

@ryan please you elaborate the formula of leaf node I think the formula is logical.

---

I think your calculation and formula u used is all correct.

But your answer by this is 63.6, why u used it as ceiling function of this. Can u explain ?

It should be 63 i think isn't it ?

Answer 4

https://en.wikipedia.org/wiki/B%2B_tree#/media/File:Bplustree.png

 

the leaf Node also contains the Block Pointer.

Answer 5

63 is correct order of leaf node .

so ans is (A) 63

Answer 6

The concept wrt leaf node of any b+ tree is :

a) 1 Block Pointer

b) Some search keys and respective record pointers

We assume that number of search keys be y.

Then number of record pointers will be y as well.

Now this becomes a simple maths equation as follows:

Size of 1Block Pointer+ Size of y search keys + Size of y Record Pointers <= 1024 B

6 + y(9) + y(7) <= 1024

y<=63.625

y= 63

ANSWER A 63