in Databases
503 views
1 vote
1 vote

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

in Databases
503 views

3 Comments

edited by
.............
0
0
edited by

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

@Vasu_gate2017 please share your approach !

0
0

1 Answer

2 votes
2 votes

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

1 comment

ok ! brute force ! thanks !
0
0