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 22.2k 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.
Best answer 69 votes 69 votes 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. Prateek kumar answered Nov 19, 2016 • edited Jun 28, 2018 by Krithiga2101 Prateek kumar comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments Satbir commented Jul 15, 2019 reply Follow Share The middle element is always chosen during a split. 0 votes 0 votes chirudeepnamini commented Nov 21, 2019 reply Follow Share @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: 3 1 2 4 now insert 5: 3 1 2 45 Now insert 6: 3 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.. OR 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 3 1 2 4 Now insert 0: 3 01 2 4 Now insert -1: 3 -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... 1 votes 1 votes s_dr_13 commented Jan 29, 2020 reply Follow Share http://www.cburch.com/cs/340/reading/btree/index.html 0 votes 0 votes Please log in or register to add a comment.
23 votes 23 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 2 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 4 2 6 8 1 3 5 7 9 10 So total 5 splits Pooja Palod answered Dec 18, 2015 Pooja Palod comment Share Follow See all 10 Comments See all 10 10 Comments reply Aryan commented Jan 6, 2016 reply Follow Share It is not B+ tree. 2 votes 2 votes Arjun commented Jan 9, 2016 reply Follow Share why replicate data? 2 votes 2 votes Pooja Palod commented Jan 9, 2016 reply Follow Share I read it as B+tree..edited now.. 1 votes 1 votes Shashank Chavan commented Jan 11, 2016 reply Follow Share How can we decide to split 2nd element in this case? Why Not 3rd element? Is there any condition for that? 0 votes 0 votes Naveen Chowdary commented Jan 12, 2016 reply Follow Share why 2nd element why cant 3rd element split 0 votes 0 votes Sriram Karunagaran commented Jan 13, 2016 reply Follow Share 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. 0 votes 0 votes indrajeet commented Nov 18, 2016 reply Follow Share if B+ tree is used then what will be the structure of the tree ?? 0 votes 0 votes Kaluti commented Mar 20, 2017 reply Follow Share We can not apply biasing in b tree and we can apply biasing only in BPlus tree is it rite? 0 votes 0 votes shivam001 commented Jan 9, 2020 reply Follow Share 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 . 0 votes 0 votes ankit3009 commented Dec 17, 2021 reply Follow Share @Kaluti please share reference for your statement. I think both trees support biasing. 0 votes 0 votes Please log in or register to add a comment.
10 votes 10 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 Tariq Husain Khan answered Sep 25, 2016 Tariq Husain Khan comment Share Follow See 1 comment See all 1 1 comment reply Hirak commented Jan 2, 2019 reply Follow Share 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 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes Answer: C Insert 10,20,30,40,5,6,15,12,17,13 (in that order). You will get five splittings. Rajarshi Sarkar answered Apr 29, 2015 Rajarshi Sarkar comment Share Follow See all 0 reply Please log in or register to add a comment.