The Gateway to Computer Science Excellence
+1 vote
what is the minimum and maximum number of keys for non-leaf nodes and leaf nodes for B+ Tree of order p?
in Databases by Loyal (5.2k points) | 211 views
Order p for both leaf and non-leaf nodes?

2 Answers

+4 votes
Best answer

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

minimum keys=(ceil of (p/2))-1

maximum keys=p-1

Now for the leaf node 

minimum keys =(ceil of (p/2))

maximum keys =p

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

by Boss (10.6k points)
selected by

Now for the leaf node 

minimum keys =(ceil of (p/2))

I Think It should be  

minimum keys =(ceil of (p/2)-1).

Because while doing questions of deletion in B+ trees the underflow condition is checked using this formula only. If the keys are less than  (ceil of (p/2)-1) then underflow . 


here the order of leaf node is 4

so Ceil (4/2)=2

so the minimum no of keys in the leaf node is 2

and after deleting it become 1 

so now they have to merge these with sibling 

now according to you

If the keys are less than  (ceil of (p/2)-1) then underflow . 


so If the keys are less than 1 then underflow

that is wrong 

right one is minimum key can be 2

for good image you can go to page 25 of the link


more information

For a 𝑏 order B+ tree (max of 𝑏 children per node)

– Find, insert, and delete are all $O(log_{b}N)$

– Space is 𝑂 (n) 

– Range queries can be done in $O(log_{b}N+K)$ for a range of 𝑘

• Range queries are queries that ask for all elements between two values – Elements in a range are already in order

+1 vote

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.

by Active (1.8k points)
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,357 answers
105,254 users