B+ Tree

Question

Consider the following $B^+$ tree with the order of internal and leaf nodes as $3$ and $2$ respectively: 

The minimum number of key insertions that causes a new level to be introduced in the above $B^+$ tree ________. (Assume key redistribution is not allowed)

Comments

How is Order defined? i.e. In What terms?

From the Diagram, it looks like Order of Internal Node is the Maximum Number of Child/Node Pointers that it contains. But same definition of Order seems not to  applying to Leaf-Nodes.

---

Usual Convention

Order of internal node : Maximum number of child a node can have

Order of Leaf node : Maximum number of Keys a node have.

---

I think its enough to add 1 key in between 42 and 51 to have a new level

Answer 1

• We need minimum 3 key insertion for new level.

Maximum key for internal =2.

Maximum key for leaf =2.

Comments

Thanku so much sir

---

Thanks abhishek