A B-tree of order 4 is built from scratch by 10 successive insertions. What is…

Answer: 5

Explanation (worst-case insertion order):

• Order 4 means a node can hold at most 3 keys.

• Insert 1, 2, 3: root accumulates 3 keys (no split).

• Insert 4: root is full so it is split → 1st split (height increases to 1).

• Insert 5: goes into a leaf (no split).

• Insert 6: causes a split of the right leaf → 2nd split (promotes a key to the root).

• Insert 7: fills a leaf (no split).

• Insert 8: splits the right leaf again → 3rd split (another promotion to root).

• Insert 9: root becomes full; splitting the root increases height → 4th split. The insertion then proceeds into a child (no further cascading split in this insertion).

• Insert 10: causes a final leaf split → 5th split. Any further splits in the same insertion do not arise in this worst-case sequence within 10 insertions.

Hence the maximum possible number of node-splitting operations over these 10 successive insertions is 5.

Brief justification of optimality: each split corresponds to an overflow corrected by splitting a node and promoting one key; using the standard split-on-the-way-down insertion strategy and a worst-case key order (e.g., increasing) achieves the above five splits, and the B-tree capacity and minimum-degree constraints prevent forcing more splits within only 10 insertions.