The Gateway to Computer Science Excellence
+2 votes
In a database file structure, the search key field is 9 bytes long, the block size is 1024 bytes, a record pointer is 7 bytes and a block pointer is 6 bytes. The largest possible order of a leaf node in a B+ tree implementing this file structure is ________.

I am getting 63 as the answer, but in the solution, it's saying 64. Can anyone check?
in Databases by (231 points)
edited by | 515 views
You didn't specify the order whether it is maximum possible pointers or maximum keys?

You have to use [P-1](K+R) +B<= 1024

Answer will be 64 only

@Anu007: Please refer this link: the same question was asked here! Kindly let me know if I am missing anything.

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

By default order is Maximum number of pointer.



u have written wrong formula

P(K+R) +B<= 1024

ans will be 63



Okay, thank you. But how to compute order in this link then:

For leaf nodes, this is the formula we should use?

 [P-1](K+R) +B<= 1024


[P](K+R) +B<= 1024

It would be great if you can kindly explain! Thanks in advance

@srestha  Can you please help! I am bit confused here. which one is correct? Maybe I can ping you in chat also. 


yes @ srestha  its 63 (order_of__leaf)*(record pointer+ key)+ block pointer<=Block size should be


In link they are Specify order which is not by default i.e. order= max number of key+ recored pointer.

By default in either leaf or Internal order is Max number of a pointer.

Given question :

In a database file structure, the search key field is 9 bytes long, the block size is 1024 bytes, a record pointer is 7 bytes and a block pointer is 6 bytes. The largest possible order of a leaf node in a B+ tree implementing this file structure is ________.

What question you are reffer:

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?

Both are not same.

in case of B+ tree the order is not same ,internal node and leaf have different order .
True! Order is not same in case of non-leaf and leaf node for B+ tree,

But if we use this:

[P](K+R) +B<= 1024

I think it's coming as 63 only.

who say this statement, the structure is different but where you got to know an order is not same.

Refere this link heading name Characteristics 

And apply formula 1st. 


@Anu007 In the link why they have taken 'n' pairs and not 'n-1' only? Won't one of the pointers in every block be a Block Pointer only? 

yes in case of non leaf the order is : order_of_node*Block_Pointer +(order_of_node-1)*key<=Block size


(order of non leaf)n=68 and for leaf order=63

Vishal without seeing my comment you are asking same question .

In isro question they define order specifically that order is max number of key and record pointer , see question 1st statement, so we have taken k not k-1.

this question and lsro question difference is they specified what they want that is not by default.


@Anu007 Yes..I got your point the first time only that they have defined order in a different way and for this question I have also got 64 as the ans. So i have understood the difference. But how the number of pairs is 'n' and not 'n-1'. Consider the image shown in wikipedia link you gave

Here n = 4 but but the number of such pairs(which are defined as Order) is still 3. NO??


yes, from wiki
necessary portion is
Leaf nodes have no children, but are constrained so that the number of keys must be at least ⌈ b / 2 ⌉ − 1 and at most b − 1 . In the situation where a B+ tree is nearly empty, it only contains one node, which is a leaf node. (The root is also the single leaf, in this case.) This node is permitted to have as little as one key if necessary, and at most b .


@ souravsaha

what is ans given there?

Can u give a screenshot

yes both formula applicable for different purposes

but I have  seen P(K+R) +B<= BS

in almost all GATE question


can u plz give brief derivation of the formula

srestha This is the screenshot. Almost all problems I solve via this P(K+R) +B<= BS only, I am not sure why (P-1)(K+R) +B<= BS is used here. 


even in Navathe same formula is used and coming out be 63

63 is right ans

here it is given that we need to find the order for B+ tree leaf node

so for that we need to know the structure of B+ tree leaf node

in B+ tree leaf node, it consists of (key+record pointer) pair and a single block pointer which points to its adjacent node.

hence the formula


Order for a node is the maximum number of pointers that the node contains.

Here, in a B+ tree, leaf node has say p pairs of key and data pointers and one block pointer.

p(key + data pointer) + block pointer <= block size

p(9+7) + 6 <= 1024


Thus p=63...........Hence Order of leaf node= Number of Pointers( Data + Block)= 63 +1= 64

@srestha  @souravsaha  @mohitbawankar...... I think the answer 64 is correct.

Kindly correct if I am wrong.

2 Answers

0 votes

Disk Block size = 1024 bytes
Data Record Pointer size, r = 7 bytes
Value size, v = 9 bytes
Disk Block ptr, P = 6 bytes

o(r + v) + p <= 1024
16o <= 1018
o =< 63

So Ans will be 63.

by Active (2.2k points)
0 votes
it is talking about leaf node just coz they didnt say anything and the value for record pointer is given .

so if u are suppose to consider it for and try to solve it then u will definately get the answer as 64 .
by (237 points)

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
50,737 questions
57,324 answers
105,169 users