in Databases edited by
18,831 views
40 votes
40 votes

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$
in Databases edited by
18.8k views

4 Comments

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

1
1
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
0
0
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.
0
0
Refer: Fundamental of Database System, 6th Ed, Navathe, Page 654

 

1
1

6 Answers

64 votes
64 votes
Best answer

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.

edited by

4 Comments

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

Please clarify.
0
0
In leaf node of B+ tree we have only one block pointer . That point to block in right side for range access .
0
0
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.
1
1
6 votes
6 votes

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.

 

2 votes
2 votes

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

4 Comments

but here question specifies order is maximum number of keys.
0
0
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.
0
0
@ryan please you elaborate the formula of leaf node I think the formula is logical.
0
0
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 ?
0
0
1 vote
1 vote

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

 

the leaf Node also contains the Block Pointer.

by
Answer:

Related questions