B+ Tree Self Doubt

Question

what is the minimum and maximum number of keys for non-leaf nodes and leaf nodes for B+ Tree of order p?

Comments

Order p for both leaf and non-leaf nodes?

---

yes

---

That depends on whether you take the left median or the right median to the parent node (after doing the split). 

https://gateoverflow.in/75163/b-tree-insertion

Answer 1

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

Comments

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 . 

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

---

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

Answer 2

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.