Indexing

---

Assume the contents of a sample recording file are on the right. It is a file with variable-length records.

How could we organize the file to provide rapid keyed access to individual records? Binary searching is not possible in a variable-length record file because direct access by relative record number is not possible.

An alternative to sorting is to construct an index for the file. An index is a list of keys, each of which identifies a unique record. Indexes make it faster to find specific records and to sort records by the index field—that is, the field used to identify each record. There are many kinds of indexes.

This figure shows a simple index, which uses simple arrays of structures that contain the keys and reference fields. A primary key for these recordings consisting of the initials for the company label combined with the recording's ID number.