406 views

2 Answers

2 votes
2 votes
Given , Each node of order = 3  and each node can hold  = 2 keys

Level 1 --- > No of keys = 2                   No of children = 3

level 2 ----> No of keys = 3 x 2             No of children = 3x3

level 3----> No of keys = 3 x 2 x 2        No of children = 3 x 3 x 3

 therefore , No of leaf node at max = 3 x 3 x 3 = 27

 

there're total 27 leaf nodes and each leaf node can hold 2 keys  = 54 keys

Now , From the given diagram we can easily see that 9 keys are already present in the leaf node

therefore , Additional number of keys that can be inserted into B + tree = 54 - 9 =  45 keys
0 votes
0 votes
Level 0 : 1 Node 3 pointers

Level 1 :  3 Node 9 pointers

Level 2 :  9 Node and each node has maximum 2 Keys = Total 18 maximum keys possible,

number of keys already present at leaf= 9 and Additional keys that can be added if height is not increased = 18 -9 = 9

Level 3 :  27 Node and each node has maximum 2 Keys = Total 54 maximum keys possible,

number of keys already present at leaf= 9 and Additional keys that can be added if height is increased by one = 54 -9 = 45

Related questions

1 votes
1 votes
0 answers
1
newdreamz a1-z0 asked Jan 2, 2019
492 views
For range queries every B+ tree index requires less I/O than a full table scan.can anyone explain?
0 votes
0 votes
1 answer
2
iarnav asked Dec 15, 2017
1,362 views
Does values in Leaf nodes of B+ tree repeats or ever leaf node has an unique value?
1 votes
1 votes
1 answer
3
6 votes
6 votes
1 answer
4
firki lama asked Jan 14, 2017
5,892 views
which formula should we use for calculating LEAF node in B+ tree?I. n*(K+r)+b<=block sizewhere n=no of keysk=key size,r=record pointer,b=block pointerII. (n-1)(K+r)+b<=bl...