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
- the index set is a B-tree of order three, which means that the maximum number of separators we can store in a node is two, and
- there is an insertion into the first block and that this insertion causes the block to split.
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.
- A new block (Block 7) is brought in to hold the second half of what was originally the first block.
- 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.
- The promoted separator, BO, is placed in the root of the index set.