Simple Prefix B+ Tree Maintenance (Cont.)


Changes Involving Multiple Blocks in the Sequence Set
These changes do change the number of blocks in the sequence set.

Insertions. For the simple prefix B+ tree in the previous slide, assume that

Since the index set for a simple prefix B+ tree is just a normal B-tree, the changes to the index set are handled just like B-tree insertion or deletion.
  1. A new block (Block 7) is brought in to hold the second half of what was originally the first block.
  2. A new separator, with a value of AY, is needed to distinguish between Blocks 1 and 7. Because the node, containing BO and CAM, is already full, the insertion of the new separator causes a split and promotion.
  3. The promoted separator, BO, is placed in the root of the index set.