Insert 75: it should go in L1 (because < 88 in I2), but no room so create new leaf L7 and split L1 between L1 and L7. This requires a new key in I2, but again there is no room, so this also must be split. To do this, create new index node I4 and adjust keys. 88 is moved to root to discriminate between I2 and I4.
Insert 572: This should go in L4, but again there is no room, so add L8 and divide content of L4. I3 is full so I5 is created and the keys are divided between I3 and I5 as before. However, the root node I1 is full so there is no room for a key to discriminate between I3 and I5. To maintain the integrity of any external references to the root, I1 is retained as root and two new index nodes, I6 and I7 are created to form the second level of the tree. I6 is used to discriminate between I2 and I4, I7 discriminates between I3 and I5.
Insert 200: This value should go into L2 but there is no room. Create L9 and divide values between L2 and L9. There is room for the new discriminator key in I4 so no further splitting occurs.
Deletions - assume the minimum fill factor below which leaf nodes are re-grouped is 50%. That is, if the number of values falls to one the node contents should be moved to an adjacent node if there is room.
Delete 67: The single value 75 is moved to L1 and L7 is removed. The keys in I2, I4 and I6 are then adjusted.
Delete 88: The value 122 is moved from L2 to L9 and L2 is removed. The keys in I2 and I4 are then adjusted and combined into I4, leaving I2 empty so it is removed. I6 is no longer needed so it is also removed. The tree must remain balanced, so keys in I7 are combined with the root node I1, and I7 is removed.
Delete 122: The value is removed from L9.
Delete 200: The value is removed from L9 leaving this leaf node below the minimum fill factor but, as there is no free space in adjacent leaf nodes, no adjustment is performed. If the minimum fill factor is strictly applied, a value could be moved from either L1 or L3 to make up the numbers in L9. This would also require a change to the keys in I4.
Delete 340: Assuming no adjustment after the previous deletion, the last remaining value is deleted from L9 and the leaf node is removed. One of the keys must now be removed from I4.
