50 votes 50 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? $3$ $4$ $5$ $6$ Databases gatecse-2008 databases b-tree normal + – Kathleen asked Sep 12, 2014 edited Jan 31, 2018 by dj_1 Kathleen 21.5k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Arjun commented Jan 30, 2015 reply Follow Share Okay. Might be resolution problem then. Image was actually well visible for me. I have now removed it and replaced with text. 1 votes 1 votes Psy Duck commented Jan 16 reply Follow Share If we are using right biased split(more elements on right after split) then answer will be $ 3$ else answer will be $5 $ so we need max of these and answer will be $5$ 0 votes 0 votes Prashant_Dubey commented Jan 26 reply Follow Share @Psy Duck For even order we prefer Right-biased only(right node will be having more nodes). 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes start inserting from 1 to 10 in a b-tree you will end up splitting it 5 times 1st split :while inserting 4 2nd split :while inserting 6 3rd split:while inserting 8 4th and 5th split :while inserting 10 Bhagirathi answered Jun 25, 2015 Bhagirathi comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes ans 3 Aditi Dan answered Dec 21, 2014 Aditi Dan comment Share Follow See all 5 Comments See all 5 5 Comments reply dhingrak commented Jan 30, 2015 reply Follow Share Please explain... 0 votes 0 votes Sriram Karunagaran commented Jan 13, 2016 reply Follow Share 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: 3 1/2 4 Now, the fifth and sixth insertions will not result in a split: 3 1/2 4/5/6 Now, the seventh insertion will create a split: 3/6 1/2 4/5 7 Now, eight and ninth insertions will not create a split: 3/6 1/2 4/5 7/8/9 Now, the tenth insertion causes split : 3/6/9 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. 2 votes 2 votes MANSINGH HANSDA commented Aug 26, 2016 reply Follow Share what is the rule for splitting , because minimum way I can split the node is 3 and the maximum way is 8 0 votes 0 votes vijaycs commented Sep 26, 2016 reply Follow Share thanks @Sriram Karunagaran, :) 0 votes 0 votes Abhijit Sen 4 commented Apr 13, 2018 i edited by Abhijit Sen 4 Apr 13, 2018 reply Follow Share 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 0 votes 0 votes Please log in or register to add a comment.