Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written?

› Category: Questions › Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written?
0 Vote Up Vote Down
Editor">Editor Staff asked 4 weeks ago

Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written?
 
(a) 14
 
(b) 7
 
(c) 11
 
(d) 5
 
Query is from B-Trees in division B-Trees of Data Structures & Algorithms I
 
I got this question during an interview.

Question Tags:
1 Answers
0 Vote Up Vote Down
Editor">Editor Staff answered 4 weeks ago

Right answer is (c) 11
 
For explanation: If s splits occur in a B-tree, 2s + 1 nodes are written (2 halves of each split and the parent of the last node split). So, if 5 splits occurred, then 2 * 5 + 1, i.e. 11 nodes are written.