Question

Suppose for insertion in a b+ tree of order 3,  the values are inserted in order 73,108,100. What will be the structure of the resulting  tree? I have watched few lectures on b+ trees and in one of the lectures by a professor from IIT KGP , inserts in a way that the resulting tree will be-

Then i watched some more lectures by some other professors and they recommended to insert in a way that will result in-

Which of the above methods should I use. I am confused as to me both seem right

Answer 1

The basic concept is that leaf node should contain all the values . U can assign internal node to the left children or the right children it's your choice the tranversal will be same . so such rule is there that u always have to assign it to left or right. its like bst deletion , u may use the biggest child of left subtree or smallest child of right subtree

Comments

So I suppose both the above methods are correct ?

---

both are correct

---

I think in the second figure, 73,100 should be in one block (as 100 is the middle value, splitting should be done at 100) , and 108 in other block, and 100 should be the parent for both the blocks ?

---

just read insertion in b + tree first . both are right.