Indexing in a Database and Types of Indexes
Indexing is a data structure technique used to rapidly find the records in a database. The index is comprised of database columns. The first column is a primary or candidate key and the second column holds the address to the disk block where the particular key can be found.
There are three types of indexing
· Primary Indexing
· Secondary Indexing
· Cluster Indexing
Primary Indexing:
The anchor attribute used for searching will be from the primary key of the table. There is always a one-to-one relationship between the number of entries in the index table and the number of address blocks. The complexity to access the searching block is
complexity to access the search block = logn+1
The primary indexing can be Dense indexing or Sparse indexing.
The anchor attribute is the first record of each block.
Dense Indexing:
In dense indexing, an index record is created for every search key. It returns searched results quickly but needs more space because an index record is created for every search key.
Sparse Indexing:
The Index record is not created for every search key instead index record points to few blocks in the index table. It needs less space and maintenance. It reduces the overhead of insertion and deletion of records. But it is slow as compared to Dense indexing.
Secondary Indexing:
Anchor attribute used for searching can be from the primary key or non-key attribute of a table. In secondary indexing, index records are not in sorted order. It is an example of dense indexing.
A tree-based index is an example of secondary indexing.
Cluster Indexing:
The anchor attribute used for searching will be a non-key attribute of the table. It is used on sorted data. It is an example of sparse indexing.
It only stores attributes and blocks pointer in the index file.
Indexing is used to search the records faster but it is not essential. The database is unaware of indexing. The indexing is optional to search the records from the database. Sometimes indexing adds the extra overhead in a database for insertion and deletion of records because, for every insertion and deletion of records, the indexing needs to be updated as well.
