Slide 14.7: A paged binary tree
Slide 14.9: Multilevel indexing (cont.)
Home

Multilevel Indexing

B-trees are the important file structure and the following approach will be taken to lead to the discussions of B-trees: 
   single record indexing ——> multirecord indexes ——> 
       multilevel indexes ——> B-trees
Single Record Indexing
This indexing was introduced in Chapter 7 and it is briefly given here again. 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. The major problem of this indexing is it becomes difficult to manage as the indexes grow. Large files need multirecord indexes.

Multirecord Indexes
The first step in extending the simple indexing strategy to support arbitrarily large data files is to break the index into multiple records in a file. A multirecord index consists of a sequence of simple index records. The keys in one record in the list are all smaller than the keys of the next record. An index of the 14 characters     A C E G H K M P Q S U W X Y ,     with 4 keys per record, would take 4 records. In the figure, the date file references are represented with dots (•).