Look up the search-key value of the record to be inserted
Dense Index - If the record is not in the index, add it. Since all key value pairs are connected via a linked list, we need to make an overflow block to store this new record.
Sparse Index - Search for the block of the file closest to the entry. Then search for the entry in the file.
In a compostite key, the sorting can be done on multiple attributes.
If the deleted record was the only record in the file with this particular search-key value, then remove it from the index as well.
Dense Index - deletion of search-key is like file record deletion
Sparse Index - if this record isn't being indexed, do nothing. If it is being indexed, then index the next element in its place. If the next element was also indexed already, drop the key-value pair.