Slide 16.7: Simple prefix B+ tree maintenance Slide 16.9: Simple prefix B+ tree maintenance (cont.) Home

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.

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.