10.3: Organization of Files

During the execution of high-level language programs, operations typically deal only with files treated as data. Operations include traversing and processing all the records of a file, randomly accessing and processing individual records selected in random order, or some combination of these two modes. The basic function of a file system, in addition to providing storage facilities, is to allow files to be searched efficiently and conveniently, so that records of an entire file may be sequentially retrieved or a portion of the file's records (perhaps only one record) may be randomly retrieved. In Example 10.1, after the bowling game scores file has been obtained, one may want to retrieve the scores of a particular game or individual.

This chapter briefly discusses the file processing facilities provided by C. It shows a number of ways in which more flexible and powerful file processing may be implemented. The literature on files would itself require a large file for its storage, and file storage and manipulation is currently an active area of research.This book considers a very small portion of that activity. The discussion deals only with the case of fixed-length records that are to be retrieved on the basis of a single field value, the primary key field. A primary key uniquely identifies a record. It is the field normally used as the search key, and the key by which records are sorted.

Just as with data structures that are stored in internal memory, the programmer must take great care to keep related records of files stored in external memory physically contiguous or linked by pointers. In internal memory, the time requirement of an algorithm is measured by the number of operations performed. These might be arithmetic operations or assignments, comparisons between two records (keys), or comparisons between two variables. When dealing with external memory, the time requirements are measured by the number of accesses to secondary storage.

10.3.1 Sequential Files