Difference between sparse index and dense index

sql database rdbms
Sabir Al Fateh picture Sabir Al Fateh · Apr 23, 2016 · Viewed 45.9k times · Source

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

Answer

Abhinav Srivastava picture Abhinav Srivastava · Jan 4, 2019

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

Related questions

Drop all tables command

What is the command to drop all tables in SQLite? Similarly I'd like to drop all indexes.

Read More
IN vs ANY operator in PostgreSQL

What is the difference between IN and ANY operator in PostgreSQL? The working mechanism of both seems to be the same. Can anyone explain this with an example?

Read More
How universal is the LIMIT statement in SQL?

I'm in the process of generalizing a Django DB replication app and it uses the statement: SELECT %s FROM %s LIMIT 1 to fetch 1 row and use the Python DBAPI to describe the fields, it works fine with ORACLE and MySQL …

Read More