The Gateway to Computer Science Excellence
+36 votes

A B-tree of order $4$ is built from scratch by $10$ successive insertions. What is the maximum number of node splitting operations that may take place?

  1. $3$
  2. $4$
  3. $5$
  4. $6$
in Databases by
edited by | 6.9k views
Add the question.
Question ??
I can't see the question!! I can only see the heading GATE 2008_41. It would be better to post the whole question.
It was there, but was an image. The images are bad and we are in the process of replacing them. I have now edited it. Are you accessing from mobile?
No I am accessing the site from my laptop.Now i can see the question.
Okay. Might be resolution problem then. Image was actually well visible for me. I have now removed it and replaced with text.

6 Answers

+55 votes
Best answer

Total 5 splitting will occur during $10$ successive insertions

Let's take $10$ successive key values as $\{1,2,3,\ldots 10\}$ which can cause maximum possible splits.



edited by
Can the answer be different if the elements were different?? How can we prove that the result will hold true for any possible series?

question asking for "maximum number of node splitting operations" so we think in worst case 

worst case will when we insert elements into same side always
nice job prateek thanks
Someone please provide me link to understand insertions and deletions in B and B+ tree properly. I am facing difficulties in this exact topic.
What would be general formula? p be order and n insertion????

@Prateek kumar

How we can choose 2 as a root in 1st split, is there any method to select 2nd element. Why 3rd element is not chosen as root ? please explain

The middle element is always chosen during a split.

@Kuljeet Shan

we can take 2 or 3 as root .But the question asks for maximum number of splits which is possible only with 2 as root..

suppose we take 3 as root..then we have:


          1 2        4

now insert 5:


          1 2        45

Now insert 6:


          12        456 $----->$No splitting is done(which is not the case when you take 2 as root)

So you are missing a split which will not give you maximum splits at the end..


If you want to take 3 as root and want maximum splits insert number<3 like 0 or -1 or -2... to get maximum splits


          1 2        4

Now insert 0:


         01 2        4

Now insert -1:


          -1 0 1  2        4 (overflow so split)

 after splitting:


                    1         3

          -1 0         2        4 

Now you won't miss any split ..

The main point is we try to populate the node which has maximum elements in order to get a split..

Hope this helps...


+22 votes

Let 1 to 10 be inserted

Insertion of 123 does not cause any split

When we insert 4 split occurs

We use right bias


   1              3456

Again on insertion of 6 split occurs

             2 4

  1         3        56

7 does not cause split

           2 4  

1         3          5678

8 cause  split

       2  4   6

1       3    5    7 8

Inserting 9 wont cause any split

       2  4   6

1       3    5    7 8 9

Inserting 10 causes split at leaf and non leaf node


    2          6   8

1    3    5   7    9 10

So total 5 splits

It is not B+ tree.
why replicate data?
I read it as B+tree..edited now..
How can we decide to split 2nd element in this case? Why Not 3rd element?
Is there any condition for that?
why 2nd element why cant 3rd element split
Third element split has been illustrated above and it does not give max number of splits. It gives only three splits. It also has to do with the type of numbers chosen.
if B+ tree is used then what will be the structure of the tree ??
We can not apply biasing in b tree and we can apply biasing only in BPlus tree is it rite?
we choose 2nd element because we want right bias[more element on right side] , if you want left bias[more element on left side] .then you can . no restriction .
+9 votes
In this ques we can splits a node with two methods which is based on chosing mid element  ,

1-Right bias (#keys in right > #keys in left or  choosing mid elem is N/2 th element ) ,then no SPLITS =5

 2-Left bias (#keys in left > #keys in left or  choosing mid elem is (N/2 +1) th element) ,then no SPLITS =3  ,where N is even.

   so, MAX # splits = 5 .

Ans is C:5

No, left biased will also produce 5 splitting operations maximum..

U are saying left bias will split 3 times as you have taken some special set of sorted inputs like 1,2,3,4,5,6,7,8,9,10  i guess,

But try this input combination 10,20,30,40,28,29,26,27,24,25 and perform left biased splitting on it.. U will get maximum splitting as 5

+4 votes
5 splitings
+4 votes
Answer: C

Insert 10,20,30,40,5,6,15,12,17,13 (in that order). You will get five splittings.
0 votes
ans 3
Please explain...
Consider the sequence 1 to 10 for insertion. Since the order is 4, the max number of keys would be 3 and min number of keys would be 1.

Now, first three insertions will not cause a split: 1/2/3

The fourth insertion causes split:


1/2          4

Now, the fifth and sixth insertions will not result in a split:


1/2          4/5/6

Now, the seventh insertion will create a split:


1/2          4/5      7

Now, eight and ninth insertions will not create a split:


1/2          4/5      7/8/9

Now, the tenth insertion causes split :


1/2          4/5      7/8      10

We have 3 splits. But, this is not the maximim number of splits. For max number of split we need insert along the leaves which have the majority elements, shown below by other users. Therefore 3 is not the right answer.
what is the rule for splitting , because minimum way I can split the node is 3 and the maximum way is 8

thanks @Sriram Karunagaran, :)

Split would be required when key items=4

If i put n/2th element in the upper level while splitting, then splits=5

Otherwise put (n/2+1) th element in upper level, then split=3

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,510 answers
95,354 users