Direct Access to a Fixed-Length Book File
A school library stores 4,800 book records in a binary file books.dat. Each record is exactly 96 bytes: accession number (4 bytes), title (60), author (24), year (4), and status (4). Records were appended in accession order, starting at accession number 1001 and running contiguously to 5800, with no deleted gaps yet. The present search program reads the file from the beginning and compares each accession number; on average it reads 2,400 records per search. The librarian wants any accession-number search to need at most three disk reads. About 2% of records are withdrawn each year and must be hidden from search, and new books are added weekly. The PC has 2 MB free RAM, and an in-memory index entry would use 16 bytes. One programmer proposes loading the whole file into an array at startup and using binary search; another proposes a linked list of records in the file.
1. Calculate the file size and the byte offset of accession number 3125 under the present layout. Show the formula and the 0-based record number.
Read the worked answer
File size = number of records × record length = 4,800 × 96 = 460,800 bytes, which is 450 KB.
Accession numbers start at 1001 and are contiguous, so the 0-based record number is:
record number = accession number − 1001
For accession 3125:
record number = 3125 − 1001 = 2124
Byte offset = record number × record length = 2124 × 96
2124 × 100 = 212,400; 2124 × 4 = 8,496; so 212,400 − 8,496 = 203,904 bytes.
The record starts at byte 203,904. A program can seek there directly with fseek(fp, 203904L, SEEK_SET) and read 96 bytes, instead of scanning 2,124 records.
2. Evaluate the array-plus-binary-search proposal. Compute the index size, state whether the 2 MB limit is a real obstacle, and explain why loading the whole file is unnecessary. Then describe an indexed-file method that meets the three-read limit.
Read the worked answer
An index entry of 16 bytes for 4,800 records needs 4,800 × 16 = 76,800 bytes, about 75 KB. That is far below the 2 MB free RAM, so the memory limit is not an obstacle. Loading the full 450 KB file would also fit, but it is unnecessary and wastes startup time.
A better method keeps a sorted index in RAM. Each entry stores the accession number and its byte offset (or record number). At startup, read the small index file-one disk read-and binary-search it in memory. Once the matching entry is found, use fseek to jump to that offset and fread the 96-byte record-a second disk read. That meets the “at most three disk reads” requirement, and the 2,400-record average scan disappears.
Binary search on the index requires the index to be sorted by accession number. New records are appended to the data file and their index entries are inserted in sorted order, so the data file itself need not be sorted physically.
3. Compare the linked-list proposal with the indexed-file approach for handling withdrawals and insertions. State how you would mark a withdrawal in each, and recommend one.
Read the worked answer
A linked list stored in the file would give each record a “next” field. Insertion can be cheap if the new record is appended and linked at the end, and withdrawal can be done by changing a status flag rather than moving records. But searching is sequential: to find accession 3125, the program may have to follow thousands of links, each requiring a disk read. It cannot guarantee three reads, so it fails the librarian's main requirement.
With the indexed file, withdrawal is a status update: binary-search the RAM index for the accession number, seek to the record, and change the status byte to “withdrawn.” The search program ignores records whose status is withdrawn. Insertion appends a new 96-byte record and inserts its accession number and offset into the sorted index; the data file is not shifted.
The linked list avoids shifting but loses direct access. The indexed file keeps direct access, handles withdrawals with one status byte, and meets the read limit, so it is the better choice here. Periodic rebuilding of the index can remove withdrawn entries if their number becomes large.