2 votes 2 votes The minimum number of elements (keys) that need to be inserted into a B+ tree with the order of internal node 3 [maximum child pointers per node] and leaf node 2 [maximum keys per node], to make it to reach 3-levels are __________. Databases databases bplustrees + – VS asked Dec 10, 2017 VS 2.1k views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply VS commented Dec 10, 2017 reply Follow Share Approach 1 : Here, Minimum fill factor : #pts/node =2 and #keys/node =1 Now, If we use minimum fill factor everywhere , we just need 4 keys Approach 2 : Constructing B+ tree i.e. if we insert keys one by one into an empty B+ tree we need 5 keys insertion for 3 levels. Which approach is correct and why ? 0 votes 0 votes Red_devil commented Dec 10, 2017 reply Follow Share i am getting 4 what is the answer? 0 votes 0 votes Ashwin Kulkarni commented Dec 10, 2017 reply Follow Share Minimum 5 keys are required! can’t do that with 4 keys in B+ trees 1 votes 1 votes VS commented Dec 10, 2017 reply Follow Share Why approach 1 is wrong ? 0 votes 0 votes Shubhanshu commented Dec 10, 2017 reply Follow Share what should be the question qording to be answer as 4? 0 votes 0 votes VS commented Dec 10, 2017 reply Follow Share @Shubhanshu I am not sure but the word "INSERT" and "to make it to reach 3-levels " is making all the difference here . The minimum number of elements (keys) that need to be inserted into a B+ tree with the order of internal node 3 [maximum child pointers per node] and leaf node 2 [maximum keys per node], to make it to reach 3-levels are __________. If it would have been The minimum number of elements (keys) in B+ tree with the order of internal node 3 [maximum child pointers per node] and leaf node 2 [maximum keys per node], and 3-levels are _________ Then answer : 4 0 votes 0 votes vamp_vaibhav commented Dec 10, 2017 reply Follow Share I think The problem with approach 1 is that it would be like a B tree in which you just filled the node with its minimal holding value.. But it would violate the property of B+ tree because you can't escalate to level until you need to split ... So it would be good to go with approach 2.. 0 votes 0 votes rahul sharma 5 commented Dec 28, 2017 reply Follow Share @vamp_vaibhav I dont see any issue with approach 1.It will not violate any property of B+tree.Just moving top to down 0 votes 0 votes vamp_vaibhav commented Dec 28, 2017 reply Follow Share So can we split without the need of splitting.. I mean if we don't have to move to next level.. We can forcibly do it in b tree 0 votes 0 votes rahul sharma 5 commented Dec 28, 2017 reply Follow Share I am not getting what you said:( If i create 3 levels of tree with min. ptr per node then i can get three levels with 4 does as mentioned by @VS. Can you give me any example what will be violated? 1 votes 1 votes vamp_vaibhav commented Dec 28, 2017 reply Follow Share Hmmm.. In the question it is saying that you have given the tree with the internal and leaf order.. You don't have three level tree initially so that you can insert directly.. Question is asking how many keys required to insert to make it to level 3..Isn't? As the approach 1 is saying to fill with minimum filling factor.. But we know to move from one level to another level we need to cross the maximum filling factor then split is performed and new level is created.. So if you go with minimum fill factor the split wont be possible.. 1 votes 1 votes Please log in or register to add a comment.
3 votes 3 votes minimum 5 key is required abhishekmehta4u answered Mar 29, 2018 abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes if you fill max then only node is going to split. 5 keys are required to reach level three 5,4,3,2,1 are keys use left baising Akash Mittal answered Dec 10, 2017 Akash Mittal comment Share Follow See all 4 Comments See all 4 4 Comments reply VS commented Dec 10, 2017 reply Follow Share Approach 1 : Here, Minimum fill factor : #pts/node =2 and #keys/node =1 Now, If we use minimum fill factor everywhere , we just need 4 keys Approach 2 : Constructing B+ tree i.e. if we insert keys one by one into an empty B+ tree we need 5 keys insertion for 3 levels. Why approach 1 is wrong ? 0 votes 0 votes prem6346 commented Dec 23, 2017 reply Follow Share https://www.cs.usfca.edu/~galles/visualization/BTree.html is it 7 0 votes 0 votes rahul sharma 5 commented Dec 28, 2017 reply Follow Share Approach 1 seems to correct to me.If they say insert into initially empty b+tree.(A usual hint given in gate questions in cases like min heap where it indirectly tells dont use build heap .) But here there is no such hint. 0 votes 0 votes Kaluti commented Jan 13, 2018 reply Follow Share for right biasing we get 5 keys and with left biasing we get 7 keys correct if i am wrong 0 votes 0 votes Please log in or register to add a comment.