Types of Ordered Indices
There are three types of ordered indices:
- Dense Index
- Sparse Index
- Multi-Level Indexing
Dense Indexing
In a dense index, for every search-key in the file, an index entry is present.
In a dense-clustering index, the index record contains the search-key value and a pointer to the first data record with that search-key value.
The remaining number of records with similar search-key value would be stored in a sequence after the first record.
Sparse Indexing
In a sparse index, an index entry appears for only some of the search-key values.
These indices can be used only if the relation is stored in sorted order of the search-key value.
To locate a record, one has to find the index entry with the largest search-key value that is less than or equal to the search-key value for which we are looking. We start looking from the record pointed to by that index entry, and then follow the pointers in the file until we find the desired record.
Multi-Level Indexing
Let’s say we have a data file with a large number of records, then Multi-Level Indexing will come to use.
As the size of the database grows, the size of the indices also grows, since a multilevel index is stored in the disk with the actual database files.
Example of a 2-Level Sparse Index
Reference Link