How the nondense index works How the nondense index worksSol

Solution

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.
   This makes searching faster but requires more space to store index records itself. Index records contain search key value and a pointer to the actual record on the disk.

A non-dense index has:
   One entry for each block
   One entry for each different value

Sparse Index is non-dense index
In sparse index, index records are not created for every search key. An index record here contains a search key and an actual pointer to the data on the disk. To search a record, we first proceed by index record and reach at the actual location of the data. If the data we are looking for is not where we directly reach by following the index, then the system starts sequential search until the desired data is found.