Difference between sparse index and dense index
As described in this link
Dense Index:
- An index record appears for every search key value in file.
- This record contains search key value and a pointer to the actual record.
Sparse Index:
- Index records are created only for some of the records.
- To locate a record, we find the index record with the largest search key value less than or equal to the search key value we are looking for.
- We start at that record pointed to by the index record, and proceed along the pointers in the file (that is, sequentially) until we find the desired record.
Also, dense indices are faster in general, but sparse indices require less space and impose less maintenance for insertions and deletions