A special application of the concept of indexes, or inverted lists, is a B-tree, which is a multilevel index
that allows both sequential and direct processing of data records. It also ensures a certain level of efficiency
in processing because of the way that the indexes are structured.
A B-tree is an index that is made up of two parts: the sequence set and the index set. (These terms are
used by IBM’s VSAM file organization documentation. You may encounter other synonymous terms.)
The sequence set is an index containing an entry for every record in the file. This index is in physical sequence,
usually by primary key value. This arrangement allows sequential access to the data records, as
follows: Process the sequence set in order, read the address of each record, and then read the record.
The index set is an index pointing to groups of entries in the sequence set index. This arrangement provides
rapid direct access to records in the file, and it is the index set that makes B-trees unique.
An example of a B-tree appears in Figure H-9, and an occurrence of this structure can be seen in Figure
H-10. Notice that the bottom row in Figure H-9, the sequence set, is simply an index. It contains an entry
for every record in the file (although for brevity, both the data records and their addresses have been
omitted). Also, notice that the sequence set entries are in groups of three. The entries in each group are
physically in sequence, and each group is chained to the next one by means of a linked list, as can be
seen in Figure H-10.
Examine the index set in Figure H-9. The top entry contains two values: 45 and 77. By following the leftmost
link (to RRN2), we can access all the records whose key field values are less than or equal to 45; by
following the middle pointer (to RRN3) we can access all the records whose key field values are greater
than 45 and less than or equal to 77; and by following the rightmost pointer (to RRN4) we can access all
the records whose key field values are greater than 77.