in Databases
687 views
0 votes
0 votes

The following key values are inserted into a B+ tree in which order of the internal nodes is 4 and that of the leaf nodes is 3, in the sequence given below. The order of the internal nodes is the maximum number of tree pointers in each node and the order of the leaf nodes is the maximum number of data items that can be stored in it. The B+ tree is initially empty: 50,15,30,40,35,20,8,10,5

The maximum number of times nodes would get split up as a result of these insertions is___?

in Databases
687 views

4 Comments

Ya..but I dont think its right..Maybe at that time I miscounted on the number of splits. I just calculated it now, Its coming as 8. How are you getting it as 4?
0
0

@Somoshree Datta 5

splits:-

1) while inserting 40

2)while inserting 8

3)while inserting 10

4)while inserting 5

 

0
0

Maximum number of splits will occur when u follow left biasing with right median as here the keys are not coming in an ordered way, i.e. keys are not decreasing or increasing.

1st leaf node split: insertion of 40

2nd  leaf node split: insertion of  35

3rd leaf node split: insertion of  20

4th leaf node split and 5th internal node split : insertion of 8

6th  leaf node split: insertion of 10

7th split leaf node split and 8th internal node split: insertion of 5

So total number of splits=8

 

0
0

Please log in or register to answer this question.