18,831 views

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?

1. $63$
2. $64$
3. $67$
4. $68$

The structure of leaf node of a B + tree is as follow

1. It single block has one block pointing to the block address of the next block

2.It has (p-1) pairs of record search key pointer and record pointer

combining 1 and 2 we get

1*Bp+(p-1)(Key+Rp)<=Block Size

Here the order of leaf nodes can be calculated as

(pLeaf*(Pr+Key))+Blockpointer<=Block size

where pLeaf is the order for the leaf nodes
Pr= record pointer
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.

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

Why you have used B Tree formula?

The B+ tree formula is: block size>=(n-1)*key size + n*block pointer.

According to this formula:

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

Hence n = 68 (Also mentioned in the question).

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.

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.

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

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 ?

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

the leaf Node also contains the Block Pointer.

by