Simple Prefix B+ Tree Maintenance
There are two kinds of changes need to be considered for maintenance:
- changes localized to single blocks in the sequence set, and
- changes involving multiple blocks in the sequence set.
Changes Localized to Single Blocks in the Sequence Set
These changes do not result in any merging, redistribution, or splitting within the sequence set.
Therefore, the index set remains unchanged.
Deletions.
The figure shows the resulting tree after the records of EMBRY and FOLKS are deleted from the simple prefix B+ tree of the previous slide.
Insertion.
Suppose, for example, that we insert a record for EATON.
- Following the path indicated by the separators in the index set, we find that we will insert the new record into Block 4 of the sequence set.
- We assume, for the moment, that there is room for the record in the block.
The new record becomes the first record in Block 4, but no change in the index set is necessary.