4.2.3 Secondary Indexes

Any of the three file access methods may have secondary indexes allowing quick access to records by field values other than the primary key. One secondary index is made of up to eight data fields, and each RMSfile may have up to 127 different secondary indexes organized as a B-tree and merged into one MS-DOS file. This file has the same name as the RMS data file but with a .i suffix attached. The RMS index file is divided into pages. The size of a page is the same as one disk block in the MS-DOS file system. In most cases, a disk block is 512 bytes.

The first two pages of an RMS index file are special; they hold the root page numbers for each of the B-tree indexes. Each page number is four bytes long. The very first page number is reserved for the primary key index in an indexed sequential file, and the rest are available as secondary indexes.

Each page in the RMS index file belongs to only one of the indexes contained in the file. At the beginning of a page, there is a small amount of prefix information followed by a set of key values and index page pointers. A key stored in the index is made up of the concatenation of each of the data fields that are indexed and the record number of the record. This record number points into the RMS data file at the record that the index entry references.

RMS functions use the record number when reading an RMSfile in secondary index order. The routines do not keep a physical pointer into the index when reading, instead the last key value is returned. This is used to find the next highest key value. If other processes have inserted or deleted records in the interim, the current location in the index is not lost.

Using B-trees is straightforward. Refer to chapter 6.4, "Sorting and Searching", in Knuth's book for more information about the techniques involved.