Fixed-Length Records

1. Consider a file of deposit records of the form:

    aaaaaaaaaaaa¯type deposit = record
   
   		 		 		 		 bname : char(22);
   
   		 		 		 		 account# : char(10);
   
   		 		 		 		 balance : real;
   
   		 		 end
   
   

   • If we assume that each character occupies one byte, an integer occupies 4 bytes, and a real 8 bytes, our deposit record is 40 bytes long.
   • The simplest approach is to use the first 40 bytes for the first record, the next 40 bytes for the second, and so on.
   • However, there are two problems with this approach.
   • It is difficult to delete a record from this structure.
   • Space occupied must somehow be deleted, or we need to mark deleted records so that they can be ignored.
   • Unless block size is a multiple of 40, some records will cross block boundaries.
   • It would then require two block accesses to read or write such a record.
2. When a record is deleted, we could move all successive records up one (Figure 10.7), which may require moving a lot of records.
   • We could instead move the last record into the ``hole'' created by the deleted record (Figure 10.8).
   • This changes the order the records are in.
   • It turns out to be undesirable to move records to occupy freed space, as moving requires block accesses.
   • Also, insertions tend to be more frequent than deletions.
   • It is acceptable to leave the space open and wait for a subsequent insertion.
   • This leads to a need for additional structure in our file design.
3. So one solution is:
   • At the beginning of a file, allocate some bytes as a file header.
   • This header for now need only be used to store the address of the first record whose contents are deleted.
   • This first record can then store the address of the second available record, and so on (Figure 10.9).
   • To insert a new record, we use the record pointed to by the header, and change the header pointer to the next available record.
   • If no deleted records exist we add our new record to the end of the file.
4. Note: Use of pointers requires careful programming. If a record pointed to is moved or deleted, and that pointer is not corrected, the pointer becomes a dangling pointer. Records pointed to are called pinned.
5. Fixed-length file insertions and deletions are relatively simple because ``one size fits all''. For variable length, this is not the case.