Next: Clustering File Organization
Up: Organization of Records in
Previous: Organization of Records in
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.
It is difficult to maintain physical sequential order as records are inserted
- 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.
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.
Tue Jul 7 16:00:21 PDT 1998