Indices

A database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space to maintain the index data structure. Some databases extend the power of indexing by letting developers create indexes on functions or expressions.

Indices are of two types:

1. Primary indices 
2. Secondary indices

PRIMARY INDICES- A file may have several indices, on the search key. If the file containing the records is sequentially ordered, a primary indices is an index whose search key also defines the sequential order of the file. These types of indices can in fact be built on any search key. 

It is of two types:-

1. Dense index-  In this, an index entry appears for every search key value in the file. In primary indices, the index records contain the search key value and a pointer to the first data record with that search key value. The rest of the records with the a,e search key value would be stored sequentially after the first record. 

2. Sparse index-  In this, an index entry appears for only some of the search key values. The sparse index can be used only if the relation is stored in the sorted order of the search keys that is if the index is a clustering index. To locate a record, we find the index with the largest search key.

SECONDARY INDICES- Secondary indices must be dense, with an index entry for every search key value. If secondary index stores only some of the search key values, records with the intermediate search key values may be anywhere in the file, and in general we cannot find them without searching the entire file. A secondary index on a candidate key looks just like a dense clustering index expect the record pointed to by successive values in the index are not stored sequentially.

Secondary indices improve the performance of queries that use keys other than the search key of the primary indices. However, they impose significant overhead on the modification of the database.