Introduction to database management systems

Indexing is used to optimize certain accesses to data (records) managed in files. For example, author catalog in a library is a type of index. Indexing is defined based on its indexing attributes. Indexing can be of following types:

• Primary Index − Primary index is defined on an ordered data file. The data file is ordered on a key field. The key field is generally primary key of relation.
• Secondary Index − Secondary index may be generated from a field which is a candidate key and has a unique value in every record, or a non-key with duplicate values.
• Clustering Index − Clustering index is defined on an ordered data file. The data file is ordered on a non-key field.

Ordered Indexing is of two types:

• Dense Index : One index entry for each search key value
• Sparse Index : One index entry for each block
  
  
  
  

Dense versus sparse indexes 

• Index size : Sparse index is smaller
• Requirement on records :Records must be clustered for sparse index
• Lookup :Sparse index is smaller and may fit in memory
• Update :Easier for sparse index 

Primary and secondary indexes

Primary index

• Created for the primary key of a table
• Records are usually clustered according to the primary key
• Can be sparse

Secondary index

• Usually dense