Primary Index! Something not to forget

Primary Key

 

Indexing in a database management system is the concept to make searching fasters. This is the biggest challenge which is to search a record from millions of records in the lowest time complexity.

 

Before discussing the primary index. Let’s see what is sparse and dense index is.

 

Sparse index: It has fewer index entries in the index file as compared to the data file.

 

Dense index: It has an equal number of index entries as the data file has.

 

To implement the primary index, we need to make sure that the primary key exists in the data file and data should be in sorted order in the data file according to the primary key.

 

If yes then primary indexing can be implemented. The primary index is a sparse index-based technique. As data is sorted, we can keep the first primary key from the data block as the key and value will be pointers to the target data block. Which is also known as an anchor record or block record. So comparatively we will have very less index entries in the index file.

Primary Index Demonstration

So time complexity in primary indexing is log₂(n)+1. In other words, every sparse index-based technique takes log₂(n)+1 as ’n’ is the number of index entries that are less than the dense index.

Always remember:

1. If data is sorted and one of the fields is unique then the sparse index is your choice.

2. If data is not sorted and there is no unique field then the unfortunately dense index is your choice.