Simple Prefix B⁺ Tree Maintenance (Cont.)

---

Changes Involving Multiple Blocks in the Sequence Set (Cont.)
Deletions. A deletion from Block 2 causes underflow and consequent merging of Blocks 2 and 3.

1. After the merging, Block 3 is no longer needed in the sequence set.
2. The separator, CAM, that once distinguished between Blocks 2 and 3 must be removed from the index set, which causes an underflow.
3. The underflow forces a merging of index set nodes, bringing BO back down into a node with the AY separator.

Summary. These two kinds of changes affect the tree's two structures:

• The sequence set: Record insertion and deletion always take place in the sequence set as if there are no index set at all.
• The index set: Index set operations are performed according to the rules for B-trees. Perform the following changes in the index set after the following tasks happen in the sequence set:
  • Split. A new separator must be inserted.
  • Merging. A separator must be removed.
  • Redistribution. The value of a separator must be changed.