8.1k views

The following key values are inserted into a $B+$ - tree in which order of the internal nodes is $3$, and that of the leaf nodes is $2$, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The $B+$ - tree is initially empty

$10$, $3$, $6$, $8$, $4$, $2$, $1$

The maximum number of times leaf nodes would get split up as a result of these insertions is

1. $2$
2. $3$
3. $4$
4. $5$
edited | 8.1k views
+1

Max is asked, so we have to use left biasing which will give 4 leaf node splits. Thus ans C)

In this question they have asked only to count leaf node splits.

So, after discussing with my friends on Facebook, I found that you will get two different answers depending on which convention you follow.

Convention 1: put the middle element in the left node, if you follow this you will get $4$ as answer.

Convention 2: put the middle element in the right node, if you follow this you will get $3$ as answer.

$4$ splits:

1. after inserting $6$
2. after inserting $4$
3. after inserting $2$ (there will be an internal node split and a leaf node split)
4. after inserting $1$

Correct Answer: $C$

edited
+2
Can you please draw the steps?
+4

Yes, true but they have clearly asked MAXIMUM number of splits which would be achieved only using left biasing B+ tree. So, 4 is the only correct answer.

0
which order you are following , is it 3 or 2 .

Please explain me this line "order of the internal nodes is 3, and that of the leaf nodes is 2"
+6
"The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it."
Read this statement from the question carefully. Both have same meaning.
+1
So there cant be unique B tree , answers can be ambiguous
+20

Those you want to visualize the tree. Draw the tree here by simply inserting the value. It will be right biased.

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

0
Which convention should be used while answering in GATE exam? convention 1 or Convention 2?
0
You're doing it completely wrong. Its clearly stated in question that order of internal node is maximum number of tree pointers in each node and they have given this order 3.

If there are 3 tree pointers then there must be 2 keys in each internal node. You have takes 3 keys in each internal node.
+6

Let me know if below is correct sequence of steps for insertion into a B+ tree (left-biased).

and Final B+ tree

Assume that from left to right leaf nodes are connected (as they are), via block pointers.

+3
0
why internal node split isn't counted here?
0

There’s an awesome B+ tree visualizer here : http://goneill.co.nz/btree-demo.php

Someone dedicated his/her time creating this great tool, and total splits are 5 according to this.

0

Best way to visualize the steps: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

I think only due to this ambiguity, whether to choose left biasing or right biasing they stopped asking such question after 2009.

I'm getting answer 3 according to above website steps.

0

@himanshu6398-Yes total 5 splits are there but 1 is of non-leaf node and question asks for the split of leaf nodes only.

0
@Ayush It seems that your leaf node containing 6 is in wrong position. It should be in the subtree immediately after 6 in the parent node
0

@Pascua-It's a left-biased B+ tree.

0

When u inserting 2, u have splitted leaf node as well as internal node

right?

But why u splitted internal node at that time?

Internal node order is 3, not 2

So, it should be inserted after insertion of 1

right??

i have tried to draw it and getting "4" split of leaf node using "left biasing"

correct me if you found any mistakes

0
@prateek.. Yes u r correct but can u pl tell me what ans are u getting if we follow right biasing.. Bcz m getting 3..with right biasing also.. Am i correct?
+2
Here, order is 3 so we can take only 2 key values in the internal nodes ,

so there should be split in the node having value 3, 4, 6 as in que --

The maximum number of times leaf nodes would get split up as a result of these insertions is asked

so ans would be 4 only .
+1

order of the internal nodes is 3 and order of internal nodes is the maximum number of tree pointers in each node

But at step 6, Your internal node has 4 poimters .

0
kapil plz help me out in this question
0
@Tauhin which part ?
0

kapil plz help in below question...

why the height of the tree will not decrease....???

https://gateoverflow.in/3537/gate2007-it-85

0
@prateek in ur ans at insert1 there are 2 split 123(at level 3)and 2346 (at level 2)

then why r u counting it as 1split .. if we consider 2split at insert1 then there are 5split...any one plz explain
0
@prateek

https://gateoverflow.in/453/gate2008-41

in the que given in above link ,last step is similar to the last step of this que ... but in that. Que split at leaf node and split at non leaf node is considered as 2split and then is this que how r u counted split at leaf node and non lead node as single split....
+1
internal node hav order 3 .. it means it will hav 2 keys ... y r u using 3 slots ??
0
@prateek in the question it is asked max no of splits at leaf nodes, you are counting even split at non-leaf node.

### SO BASICALLY RIGHT BIASED has 3 splits.

THANK YOU

Correct me if I am wrong !!

edited
+1
leaf node will hav 2 keys ... and internal node will hav 2 keys as order is 3 ...
0
@puja ... is my diagram wrong? explain where did i go wrong?
+1

leaf and internal nodes will hav 2 keys ...

0
Both Left and right biased diagram are correct.

In right step 6 is 2 split one is from leaf and second one is from internal node.

answer is 3 if followed right biasing, means, putting middle element in right node.
and, answer is 4 if followed left biasing, means, putting middle element in left node.

but actually, which to follow officially ?
however, maximum is asked in this question, so ,there is a reason to choose left biasing here.

using left biasing the ans should be 4 but using right biasing 3. in ques it is not mention to use which biasing only mention isThe maximum number of times leaf nodes would get split up as a result of these insertions is so the correct ans should be only

0
answer according to geeks for geeks is 3. Plz suggest whether we should use right biasing or left biasing.
If data is given in  either descending order or unsorted order  -  Left biasing will give Maximum leaf spilt...

If data is given in ascending order  -  Right biasing will give Maximum leaf split...

Here it is unsorted order... Therefore maximum leaf split = 4 by left biasing
–1 vote

Ans: B

3 leaf  splits

1. after inserting 6

2. after inserting 8

3. after inserting 2

0
but at the tym of insertion of 6 only one node will be there so that must be considered as a root node , so why to count that..??
–1 vote
left biased 4 splits and right biased 3 splits... trying to add the image for it
edited
3 splits

1. after inserting 10

2. after inserting 8

3. after inserting 2
+6
How on this earth would 10 cause a split. That is the first value that get inserted in the tree !!!

I hope you are not confusing it with B- Tree.Because may result in 3 leaf node splits in this case but for B+ tree answer is 4 (as Vikrant said above).
It should be B . 3 leaf nodes

overall  3 leaf nodes + 1 Internal node
0
no it should be c

1
2