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.
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 Show 7 previous comments 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.