Overview

THIS CHAPTER CONTINUES THE DISCUSSION of file operations begun in Chapter 15. It deals with indexed files, which have a much richer structure than sequential files.

An indexed file consists of a set of records, each of which is composed of individual fields. A field is a portion of a record containing one item of information, such as a user name or a Social Security number. An indexed file record can contain any number of fields. There is no requirement that all the records in a file have the same field layout; there can be various types of records, each with its own layout. If all the records in a file have the same length, then the indexed file can have fixed-length records. Otherwise the file must contain variable-length records.

What distinguishes indexed files from sequential files are the key fields in a record. A key field, or simply key, is a field whose values are to be indexed for fast lookup. An index for each key field is maintained in a section of the file separate from the data records. The index for a particular key contains an entry for each record in the file, the entry matching the record's key with the record's location in the file. The index is sorted such that a given key can be found quickly and the corresponding record or records retrieved. The indexes thus allow records to be retrieved randomly by key.

Every indexed file has...