Project ForgeThe following key values are inserted into a B+-tree in which the order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below: 10, 3, 6, 8, 4, 2, 1. The B+-tree is initially empty. What is the maximum number of times leaf nodes would get split up as a result of these insertions?
Explanation
With max 2 items per leaf, tracing insertions 10,3,6,8,4,2,1: inserting 6 overflows the first leaf {3,6,10} — split 1. Inserting 8 overflows {3,6,8} — split 2. Inserting 4 overflows {3,4,6} — split 3. Inserting 2 overflows {2,3,4} — split 4. Inserting 1 overflows {1,2,3} — split 5. Total leaf splits = 5 (two of these insertions also trigger an internal-node split, but those aren't counted here).
Source: GATE CS 2009 (2009)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.