1,600 views
2 votes
2 votes
what is the minimum and maximum number of keys for non-leaf nodes and leaf nodes for B+ Tree of order p?

2 Answers

Best answer
9 votes
9 votes

For non leaf node  where p is the order of non leaf

minimum keys=$\lceil$$\frac{p}{2}$ $\rceil$ $-1$

maximum keys=p-1

Now for the leaf node 

minimum keys =$\lceil$$\frac{p}{2}$ $\rceil$

maximum keys =p

because the order of leaf node is the maximum no of keys value pair in the leaf node

edited by
2 votes
2 votes

Order for leaf node in B+ tree= Block pointer + order of leaf node(record pointer + key )<= block size

Order for non leaf node in B+ tree= order * index pointer + (order-1)*keysize<=block size

In the b+ tree there is no record pointer in internal node there is record pointer present at only leaf node so here n-1 i think it may help you.

Related questions

0 votes
0 votes
1 answer
1
aditi19 asked Nov 23, 2018
406 views
can anyone share some good resources fot B+ tree deletion?
6 votes
6 votes
1 answer
2
Habibkhan asked Oct 19, 2016
1,074 views
Q : One basic doubt that is coming to my mind is whether number of splits in the process of insertion in B+ Tree indexing going to change if we consider left biasing and ...
2 votes
2 votes
0 answers
3
Manu Thakur asked Oct 26, 2017
1,942 views
In the following question, How to know that at first level (base level) index entries will be recorded for a block or for each record?https://gateoverflow.in/2311/gate199...
0 votes
0 votes
0 answers
4
bts1jimin asked Jan 9, 2019
375 views
Can anyone suggest me any useful source from where I can read b+ tree insertion and deletion?