B/B+ Tree

Question

Order P=5 ( Max Child pointer )

If Keys are inserted in the sequence of 1,2,3,4,5...................Then which is the 1st key insertion that leads to level 4 

(i) B Tree

(ii) Left Biased B⁺ Tree

(iii) Right Biased B⁺ Tree

Comments

.............

---

For B TREE:

Insertion sequence 1,2,3,4,5,6,....

For $P=5$ internal nodes will be filled with 2 keys and produce 3 pointers for the next level except the rightmost nodes which will be full with respect to the required criteria.

We have x levels and a new key K , is going to be inserted. Because of that a new level $(x+1)$ will be initiated. In this configuration following recurrence relation holds.

• No of child pointers from $n-1$ level to $n$ level is $\text{F(n)}= 2+3. \text{F(n-1)}$ for $n > 1$ with $\text{F(1) = 1}$
• No of keys in nth level = $\text{F(n)} * 2 + 2$ 

So,

• No of keys in 1th level = 4
• No of keys in 2th level = $\text{F(2)}*2+2 = 12$
• No of keys in 3th level = $\text{F(3)}*2+2 = 17*3+2 = 36$
• Till now $(4+12+36) = 52$ distinct keys inserted.
• $\Rightarrow$ next key $K = 53$

---

@Vasu_gate2017 please share your approach !

Answer 1

@debashish deka.... I solved by drawing and observing pattern in b tree

Comments

ok ! brute force ! thanks !