B tree gate 2008
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?
(A) 3
(B) 4
(C) 5
(D) 6
5Comments
Pritam Prasun @pritam
26 Oct 2016 10:28 am

You need to insert elements in B tree with an intension to create maximum unbalance.

As the order given is 4, a node can not have more that 4 children and hance it can not hold more than three keys.

Please proceed in this direction. After each split, focus on inserting keys in only one node.

Arjun @arjunsinghra
26 Oct 2016 03:59 pm

ans is 5

order 4  B-tree where maximum no of keys required 3

if we try to insert more then 3 key into the node overflow will occur.
then node will splitting into 3 parts "left node", "right node" and "parent node"  ,mid of  keys goes to parent node left part of the mid goes to left node  and right part of the mid  goes to the right node

Note: if order of the B-tree is  'O' then maximum no of keys requierd "O-1"  
during splitting if no of keys are even then 
1) no of keys in root node is 1
2) no of keys in left node is floor((O-1)/2)
2) no of keys in right node is floor(((O-1)/2)+1)

during splitting if no of keys are odd then 
1) no of keys in root node is 1
2) no of keys in left node is (O-1)/2
2) no of keys in right node is (O-1)/2)

Pritam Prasun @pritam
26 Oct 2016 09:05 pm

@arjunsinghra, Nice and clear answer.

Arjun @arjunsinghra
26 Oct 2016 09:56 pm

thanks sir

Ruchika @ruchikalakhi
26 Oct 2016 07:48 pm

Okk .thanks...

Pages