The Gateway to Computer Science Excellence
+2 votes

Database file consist 50000 records with record size 100 bytes, block size 512 bytes. If sparse B+ tree index build over given database file with search key size 20 bytes both block pointer and record pointer sizes 12 bytes each. How many maximum index blocks required if node order P is defined as between ⎡P/2⎤ to P pointers per node?

in Databases by Loyal (7k points) | 468 views

1 Answer

+7 votes
Best answer

Record Size = 100 B
Block Size = 512 B

Hence, We can say, $\left \lfloor \frac{512}{100} \right \rfloor$ = $5$ records per block (Unspanned organisation assumed by default)

So, Number of block required for Database table = $\left \lceil \frac{50000}{5} \right \rceil = 10,000$ Blocks

Now, Let's find the Order $P$ of B+ tree.

Search Key size = 20 B
Pointer size = 12 B
And Order is defined as usual convention.

So, $(P-1)20 B + (P \times 12 B) \leq 512B$

Hence, $P = 16$

So, In any node of B+ tree, Minimum $\left \lceil \frac{P}{2} \right \rceil -1 = 7$ Keys should present.

Since, We are asked to make the Maximum index blocks in the B+ tree index, So, for that, We will try to fill each Index block as less as possible. Hence, We will try to put only $7$ keys per block.

Here, For B+ trees we can apply Bulk-loading concept. Since there are 10,000 blocks in the database relation.... For Sparse B+ tree index, We need to store 10,000 keys in the Index. 

So, At the Bottom level (I am naming  it 1st level)  of Index, Putting 7 keys per node.. We need $\left \lfloor \frac{10000}{7} \right \rfloor = 1428$ Nodes.

Now, at next upper level (2nd level), We need $1428$ Node Pointers. And Since, We can put minimum 8 pointers per node, We would need $\left \lfloor \frac{1428}{8} \right \rfloor = 178$ Nodes

So, Now, at next upper level (3rd level), We need 178 Node pointers. Hence, $\left \lfloor \frac{178}{8} \right \rfloor = 22$ Nodes.

Going on same way, On next upper level (4th level), We need 22 Node pointers. Hence, $\left \lfloor \frac{22}{8} \right \rfloor = 2$ Nodes.

And finally, at the root level, We can have 2 Node pointers, Hence, 1 Block.

So, Maximum number of Index Blocks required = $1428 + 178 + 22 + 2 + 1 = 1631$ Blocks.

by Boss (27.3k points)
selected by
Why'd you take floor why not ceil because sir here it's asked about nodes when one node we can store 7 keys and 1428*7 = 9996 not 10000 so 4 keys we missed so it  should be ceil isn't it ?
yes it should be ceil not floor

till 1428th node all the nodes will be filled. now minimum occupancy at leaf is ceil(p/2)-1=7

the 9996 keys are already distributed leaving 4 keys left which will be in 1429th node

so keys will be re-distributed b/w 1428th and 1429th node

The answer is Correct. 

1428*7 = 9996 not 10000 so 4 keys we missed so it  should be ceil isn't it ?

These 4 keys will be put in some of those 1428 Index blocks. You can't make new separate Index block for them because it'd violate the minimum occupancy criteria.  

so keys will be re-distributed b/w 1428th and 1429th node

Say it were correct. Now you have 7 keys in 1428th node and 4 keys in 1429th node. Now you are saying that we re-distribute these 11 keys in these two nodes without violating the minimum occupancy criteria.. I don't see that possible.  


ah! got it now.... 11 keys cannot be re-distributed among two nodes such that both nodes will have min 7 keys

yes you're correct @Deepakk Poonia (Dee)


$(P-1)20 B + (P \times 12 B) \leq 512B$

this formula isnot for order of leaf nodes of B+ tree



@Deepakk Poonia (Dee)

Moreover in nptel min no of keys is $\left \lceil \frac{p}{2} \right \rceil$

and even wiki too

maximum index blocks

means max nodes, right??

Another doubt from wiki

Is branching factor and order means same for $B+$ tree??

Then max no. of keys will be $(p-1)$ and min be $\left \lceil \frac{p}{2} \right \rceil$


for B+ Tree

order of leaves=max number of keys

order of internal nodes=max number of block pointers or what you call branching factor

for both internal and leaf nodes, max number of keys is p-1 and minimum number of keys=$\left \lceil \frac{p}{2} \right \rceil-1$

p is the overall order of tree

see this text from Korth

for leaf: (p-1)(k+r)+b<=block size
for internal nodes: (p-1)k+p*b<=block size


U have written wrong formula for leaf

It should be  p(k+r)+b<=block size

And this formula should be used in this question


because, first of all we need order of leaf level node.


that is the correct formula

p is the max order of a B+ tree

the leaf nodes will have max p-1 keys and thus p-1 record pointers

according to your formula, a leaf of B+ tree will have p keys and p record pointers which is incorrect

you can use any formula. you'll get the same result


Donot use any wrong formula

Otherwise, u will get -ve marks in GATE for sure.

Because in that exam 0.00xx matters



see this
in any solution you'll find these formulas are used

for leaf: (p-1)(k+r)+b<=block size
for internal nodes: (p-1)k+p*b<=block size



I am telling about leaf node :(

Plz properly chk my comments


ok assume your formula is correct

It should be  p(k+r)+b<=block size

now a leaf node can have max p-1 key pointers. correct?
here p is the max order of the B+ tree
but according to your formula the leaf can have max p key pointers
use the formula and try to draw the leaf node
you'll understand 

In B+ tree in it's leaf node, there should be p key pointers

Because it has totally different representation from other node

It would be like this

$\left \langle \left \langle K_{1},R_{1} \right \rangle,\left \langle K^{2},R_{2} \right \rangle,\left \langle K_{3},R_{3} \right \rangle,.......{\color{Red} {R_{next}}} \right \rangle$

where $R_{1},R_{2},......$ are key pointers

and $R_{next}$ is block pointer.

So, for eack block size, the size of $p$ key pointer and 1 block pointer should be included in it

here p is order of leaf only. overall order of tree will be p+1

because that one block pointer is not counted but all block pointers of internal nodes are counted

order of B+ Tree leaf is max number of keys and order of internal nodes is max number of block pointers

if the order of B+ Tree is p then formula is (p-1)(k+r)+b<=block size

No, there order of leaf is $p$ and overall order also be $p. $ Because block pointer is not used to count order in $B+$ tree leaf nodes. Only record pointer count it
are u saying the internal nodes will have p block pointers and leaves will have p keys?

So, what will be $p$ for above question??

see this solution
formula for leaf is given

if order of B+ Tree is p
then leaf node will have p-1 keys not p keys



That is the correction needed for that question.


Nope. it's correct actually
I found out later


Plz correct the formula first. U r going wrong :(

chk here



in that question n is the max no. of keys in the leaf

lets say all nodes are completely filled in all levels

if order of B+ tree is p then all internal nodes will have p-1 keys... right? and all internal nodes will have p block pointers

in case of leaves it'll also have p-1 keys(which happens to be the order of leaf)
now leaf also has p pointers but one of them points to the right sibling that is why it is not counted
[there are p-1 record pointers in leaves and 1 block pointer]

P.S. leaves don't have block pointer(that one 1 block pointer to right sibling is not counted]. leaves have record pointers

I may be wrong. then pls provide me some authentic resource for the formula

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,257 answers
104,735 users