Indexing in DBMS: What is, Types of Indexes with EXAMPLES

What is Indexing?

Indexing is a data structure technique that allows you to quickly retrieve records from a database file. An index is a small table having only two columns. The first column comprises a copy of the primary or candidate key of a table. Its second column contains a set of pointers holding the address of the disk block where that specific key value is stored.

An index:

• Takes a search key as input.
• Efficiently returns a collection of matching records.

Without an index, the database must scan every row to answer a query. With one, it jumps straight to the matching block, which is why the index type chosen has a large effect on performance.

Types of Indexing in DBMS

Indexing in a database is defined based on its indexing attributes. The two main types of indexing methods are:

• Primary Indexing
• Secondary Indexing

Primary Index in DBMS

A primary index is an ordered file of fixed length size with two fields. The first field is the same as the primary key, and the second field points to that specific data block. In the primary index, there is always a one-to-one relationship between the entries in the index table.

The primary index is also further divided into two types:

• Dense Index
• Sparse Index

Dense Index

In a dense index, a record is created for every search key value in the database. This helps you search faster but needs more space to store index records. In this method, records contain the search key value and point to the real record on the disk.

Sparse Index

A sparse index is an index record that appears for only some of the values in the file. Sparse index helps you resolve the issues of dense indexing in DBMS. In this technique, a range of index columns stores the same data block address, and when data needs to be retrieved, that block address is fetched.

A sparse index stores index records for only some search-key values. It needs less space and less maintenance overhead for insertions and deletions, but it is slower than the dense index for locating records.

Below is a database index example of a sparse index.

Dense Index vs Sparse Index

The two primary index variants make opposite trade-offs, summarised below.

Aspect	Dense Index	Sparse Index
Entries	One per search key	One per block
Space	More	Less
Search speed	Faster	Slower
Maintenance	Higher	Lower

Secondary Index in DBMS

The secondary index in DBMS can be generated by a field that has a unique value for each record, and it should be a candidate key. It is also known as a non-clustering index.

This two-level database indexing technique is used to reduce the mapping size of the first level. For the first level, a large range of numbers is selected, so the mapping size always remains small.

Secondary Index Example

Let us understand secondary indexing with a database index example. In a bank account database, data is stored sequentially by acc_no, but you may want to find all accounts in a specific branch of ABC bank.

Here, you can have a secondary index for every search key. The index record points to a bucket that contains pointers to all the records with that specific search-key value.

Clustering Index in DBMS

In a clustered index, the records themselves are stored in the index, not pointers. Sometimes the index is created on non-primary key columns, which might not be unique for each record. In such a situation, you can group two or more columns to get unique values and create an index, which is called a clustered index. This also helps you identify the record faster.

Example: assume that a company has recruited many employees in various departments. In this case, a clustering index should be created for all employees who belong to the same department.

They are considered as a single cluster, and the index points to the cluster as a whole. Here, Department_no is a non-unique key.

What is a Multilevel Index?

Multilevel indexing is created when a primary index does not fit in memory. In this type of indexing method, you can reduce the number of disk accesses to reach any record. The records are kept on a disk as a sequential file, and a sparse index is created on top of that file.

B-Tree Index

The B-tree index is the most widely used data structure for tree-based indexing in DBMS. It is a multilevel format of tree-based indexing that uses balanced binary search trees. All leaf nodes of the B-tree hold the actual data pointers.

Moreover, all leaf nodes are interlinked with a linked list, which allows a B-tree to support both random and sequential access.

• Leaf nodes must have between 2 and 4 values.
• Every path from the root to a leaf is mostly of equal length.
• Non-leaf nodes apart from the root node have between 3 and 5 child nodes.
• Every node that is not a root or a leaf has between n/2 and n children.

Where exact-match lookups dominate and range scans are rare, hashing can be a faster alternative to a B-tree index.

Advantages of Indexing

The important advantages of indexing are:

• It helps reduce the total number of I/O operations needed to retrieve data, so you do not need to access a row directly from the table.
• It offers faster search and retrieval of data to users.
• It can reduce tablespace, because you do not need to store the ROWID in the index for every linked row.
• Data in the leaf nodes is already ordered by the value of the key.

Disadvantages of Indexing

The important drawbacks of indexing are:

• To perform indexing, you need a primary key on the table with a unique value.
• You cannot build another index on data that is already index-organized in the same way.
• You are not allowed to partition an index-organized table.
• Indexing decreases performance in INSERT, DELETE, and UPDATE queries.

FAQs