Types of Single-Level Ordered Indexes

The idea behind an ordered index is similar to that behind the index used in a textbook, which lists important terms at the end of the book in alphabetical order along with a list of page numbers where the term appears in the book.

For a file with a given record structure consisting of several fields (or attributes), an index access structure is usually defined on a single field of a file, called an indexing field (or indexing attribute).1 The index typically stores each value of the index field along with a list of pointers to all disk blocks that contain records with that field value. The values in the index are ordered so that we can do a binary search on the index. If both the data file and the index file are ordered, and since the index file is typically much smaller than the data file, searching the index using a binary search is a better option.


Types of Single-Level Ordered Indexes:
  • Primary Indexes
  • Clustering Indexes
  • Secondary Indexes

There are several types of Ordered Indexes. A Primary Index is specified on the ordering key field of an ordered file of records. If the ordering field is not a key field that is, if numerous records in the file can have the same value for the ordering field another type of index, called a Clustering Index, can be used. A third type of index, called a Secondary Index, can be specified on any non-ordering field of a file. A data file can have several secondary indexes in addition to its primary access method.