+1 vote
211 views
what is the minimum and maximum number of keys for non-leaf nodes and leaf nodes for B+ Tree of order p?
| 211 views
0
Order p for both leaf and non-leaf nodes?
0
yes

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
0

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 .

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

ceil(4/2)-1=1

so If the keys are less than 1 then underflow

that is wrong

right one is minimum key can be 2

https://classes.engineering.wustl.edu/cse530/notes/CSE530A-23-B+-Trees.pdf

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

0

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)