Dense And Sparse Indices

Dense Index

In a dense index, a key-value pair is stored for every index in the table. A dense index on a certain attribute of a table stores pointers to the first element where the value of this attribute changes, in a table sorted by this attribute.

Sparse Index

A sparse index contains records for only some search-key values. This is only sensible when the records are ordered by the search key. These take less space to store than the dense indexes, but are also slower.

Note that secondary records always have to be dense indices, since the records wont be sorted in their order.

Clustering vs. Non-Clustering Indices

• Sequential scan with a clustering index is cool, because it minimises number of blocks that have to be loaded in from memory.
• Sequential sacn on a non-clustering index is much slower because blocks have to be repeatedly loaded and unloaded.'

Multilevel Index

A multilevel index is used when even the index is too large to fit in memory. We keep the index as a sequential file and create another sparse index on the index. This is called a multilevel indexing system. It leads to even more insertion / deletion overhead.