9.2k 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$ $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$

edited | 9.2k views
0

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

0
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

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

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

$n \leq$ $63.625$.

So, $63$ is the answer.

by Boss (19.9k points)
edited
0
Why did you add the value of block pointer(i.e. 6) .. B± tree leaf contain only key and record pointer?
+1
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?
0
@ 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.
0
How can key be multiplied with P. If P is the order then it shud be

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

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

+2

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

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

0

ur formula is not correct.

See from any standard book

+5

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

+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
0
@student2018 is correct @srestha , even I too have same doubt as @student2018 ,

for leaf node

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

and

for other than leaf node

P.blockptr+(P-1)keys<=block PTR
0
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?
0

@Warlock lord 1KiloByte = 1024 Bytes

1Kilogram= 1000 grams

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

0
@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.
0

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

0
Please provide the actual formula and reference for the formula of leaf node , it is too confusing.

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.

by Active (2k points)
+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

by Active (3.6k points)
0
but here question specifies order is maximum number of keys.
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
@ryan please you elaborate the formula of leaf node I think the formula is logical.
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 ?
63 is correct order of leaf node .

so ans is (A) 63
by Junior (765 points) https://en.wikipedia.org/wiki/B%2B_tree#/media/File:Bplustree.png

the leaf Node also contains the Block Pointer.

by Active (1.4k points)

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 ?
by (11 points)