13.1

Consider the deletion of record 5 from the file of Figure 13.3. Compare the relative merits of the following techniques for implementing the deletion:

  1. Move record 6 to the space occupied by record 5, and move record 7 to the space occupied by record 6.

  2. Move record 7 to the space occupied by record 5.

  3. Mark record 5 as deleted, and move no records.

  1. Although moving record 6 to the space for 5 and moving record 7 to the space for 6 is the most straightforward approach, it requires moving the most records and involves the most accesses.

  2. Moving record 7 to the space for 5 moves fewer records (than option a) but destroys any ordering in the file.

  3. Marking the space for 5 as deleted preserves ordering and moves no records, but it requires additional overhead to keep track of all of the free space in the file. This method may lead to too many “holes” in the file, which if not compacted from time to time, will affect performance because of the reduced availability of contiguous free records.