Sequential File Organization

1. A sequential file is designed for efficient processing of records in sorted order on some search key.
   • Records are chained together by pointers to permit fast retrieval in search key order.
   • Pointer points to next record in order.
   • Records are stored physically in search key order (or as close to this as possible).
   • This minimizes number of block accesses.
   • Figure 10.15 shows an example, with bname as the search key.
2. It is difficult to maintain physical sequential order as records are inserted and deleted.
   • Deletion can be managed with the pointer chains.
   • Insertion poses problems if no space where new record should go.
   • If space, use it, else put new record in an overflow block.
   • Adjust pointers accordingly.
   • Figure 10.16 shows the previous example after an insertion.
   • Problem: we now have some records out of physical sequential order.
   • If very few records in overflow blocks, this will work well.
   • If order is lost, reorganize the file.
   • Reorganizations are expensive and done when system load is low.
3. If insertions rarely occur, we could keep the file in physically sorted order and reorganize when insertion occurs. In this case, the pointer fields are no longer required.