Dense Index
An index record is created for every row of the table.
- Records can be located directly as each record of the index holds the search key value and the pointer to the actual record.
Sparse Index
Index records are created only for some of the records. To locate a record:
- find the index record with the largest search key value <= the search key value we are looking for
- start at that record pointed to by this index record and proceed along the pointers in the file (that is, sequentially) until we find
the desired record
While Dense Indexes are great for search and select operations they are more expensive to maintain when compared to Sparse indexes.
Reference Notes