'Difference between sparse index and dense index

I am very confused to understand the difference between sparse index and dense index. Can you explain the difference between them ?

sqldatabaserdbms


Solution 1:[1]

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.

Visualisation of Index Record as a two column table, first column has name of the cities and second column has a direct pointer to the actual row of the cities table

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

Visualisation of Index Record as a two column table, first column has name of the cities and second column has a direct pointer to the actual row of the cities table but not all entries in index table correspond to the main table

While Dense Indexes are great for search and select operations they are more expensive to maintain when compared to Sparse indexes.

Reference Notes

Solution 2:[2]

In Dense Index, an index entry appears for every search-key whereas for Sparse index, an index entry appears for only some of the search-key values.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2

Related Questions