The Gateway to Computer Science Excellence
+32 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$ $bytes$, data record pointer is $7$ $bytes$ long, the value field is $9$ $bytes$ long and a block pointer is $6$ $bytes$ long, what is the order of the leaf node?

  1. $63$
  2. $64$
  3. $67$
  4. $68$
in Databases by
edited by | 10.7k views

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

6 Answers

+53 votes
Best answer

The answer is option A.

Bp + P(Rp + Key ) $\leq$ BlockSize

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

$n \leq$ $63.625$.

So, $63$ is the answer.

edited by
Why did you add the value of block pointer(i.e. 6) .. B± tree leaf contain only key and record pointer?
I know the equation to calculate

n*p + (n-1)*(k+q) <= Block Size

where n=order

p= block pointer

k=key size

q=record pointer

Then why are we multiplying 6 by 1 and not by n?
@ Jhunjhunuwala  

You should have a look at the structure of a leaf node of the B+ tree. It has a block pointer pointing to the next leaf node.
How can key be multiplied with P. If P is the order then it shud be

(P-1)*keysize + P*recordPointerSize +Bp<= block size

harveen singh   the formula you are saying is for B tree.


B_p + P(Rp + Key ) ≤≤ BlockSize is taken why not 

B_p +(P-1)(Rp + Key ) ≤≤ BlockSize


@ student2018  

ur formula is not correct.

See from any standard book


The order of a leaf node in a B++ - tree is the maximum number of (value, data record pointer) pairs

it totally depends on person to person as some one can define order as max keys in any node or max block pointer in inter nal node or max(keys, block pointer) etc

but universal fact is that in any node max if max key can be stored is k then max record pointer must be one more than that,

here in this question p=data record pointer so max key can be atmost p-1

@sresta one doubt for me is

 Is it because of

The order of a leaf node in a B++ - tree is the maximum number of (value, data record pointer) pairs it can hold.

Here in question it self order means max number of value, data pointer

As per question we considered it as P

But if nothing mentioned we just consider P-1 keys

Is my understanding is meaningful
@student2018 is correct @srestha , even I too have same doubt as @student2018 ,

for leaf node

(p-1)(key+record PTR)+1block PTR <=blocksize


for other than leaf node

P.blockptr+(P-1)keys<=block PTR
There was a comment I had read under on of the answer to a question here on GO stating that if it's 'K' then we have to consider 1000 and if it's 'k' we must consider 1024. Why didn't we apply the same logic here? If the option had 62 and 63 both, what could have been the solution?

@Warlock lord 1KiloByte = 1024 Bytes

1Kilogram= 1000 grams

Kilo in decimal and binary are different.  Here it is binary 'Kilo'.

@junk I am aware. But in a lot of solutions in Compute Networks they have considered 1000 and not 1024 .. of course to get away with the easy calculation but this creates a confusion when to use what. And what I posted earlier was mentioned by one of the 'Boss' so I wanted to confirm.

@Warlock lord you might have seen them in bandwidth calculations. please note that when we say 1Kbps , it is kilo in SI units standard and we are saying 1000 bits per second. when we say 1KBps , it is kilo in JEDEC units standard and it is defined to be $2^{10}$ or 1024Bytes per second. 

if anyone used 1KBps to be 1000Bps, it is wrong, but we can use to approximate the answers quickly to save time. 

Please provide the actual formula and reference for the formula of leaf node , it is too confusing.
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:


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

Please clarify.
+4 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


                    n <= 63.6

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


+1 vote

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 ?
+1 vote


the leaf Node also contains the Block Pointer.

0 votes
63 is correct order of leaf node .

so ans is (A) 63
–5 votes
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  



It is a correct ?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,503 answers
95,331 users