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 15a. 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
