Index Update

Regardless of what form of index is used, every index must be updated whenever a record is either inserted into or deleted from the file.

1. Deletion:
   • Find (look up) the record
   • If the last record with a particular search key value, delete that search key value from index.
   • For dense indices, this is like deleting a record in a file.
   • For sparse indices, delete a key value by replacing key value's entry in index by next search key value. If that value already has an index entry, delete the entry.
2. Insertion:
   • Find place to insert.
   • Dense index: insert search key value if not present.
   • Sparse index: no change unless new block is created. (In this case, the first search key value appearing in the new block is inserted into the index).