Maximum number of node splitting operations of a B-tree

Q.  Algorithms: Consider a B-tree of order 4 and is built from scratch by 10 successive insertions. What would be the maximum number of node splitting operations that take place?
- Published on 24 Jun 15

a. 6
b. 3
c. 4
d. 2

ANSWER: 4
 
A B-tree of order m contains n records and each contains b records on average then the tree will have about n/b leaves. If we split k nodes along the path from leaves then
k<=1+logm/2 [n/b]
here n=10,b=3,m=4 so
k<=1+log4/2 [n/b]
k<=1+log2 4
k<= 1+2
k<=3

Post your comment / Share knowledge


Enter the code shown above:
 
(Note: If you cannot read the numbers in the above image, reload the page to generate a new one.)