Indexing in DBMS

⏱ Estimated reading time: 3 min

Indexing in DBMS is a technique used to improve the speed of data retrieval operations on a database table. An index is a small, separate data structure that allows the DBMS to locate and access records faster, just like an index in a book.

Without indexing, a DBMS has to search through every record (called a full table scan), which is slow for large tables. Indexing reduces the time complexity of searching from O(n) to O(log n) or even O(1) depending on the type of index.

Why Indexing is Needed?

Indexing improves:

• Search speed

• Sorting and ordering

• JOIN performance

• Query optimization

Example:
Searching for a student with RollNo = 101 in a table of 1 million rows becomes very fast using an index.

How Indexing Works?

An index stores:

• Key (attribute value)

• Pointer to the actual record

Example:
Index on RollNo stores:

DBMS uses the index to jump directly to the required record.

Types of Indexing in DBMS

1️⃣ Primary Index

• Created on the primary key of the table.

• Entries are stored in sorted order.

• Table must be stored in sequential file organization.

Example:

Student(RollNo, Name, Course)
Primary Index on RollNo.

2️⃣ Secondary Index

• Created on non-primary key attributes.

• Supports faster access using attributes like Name or City.

Example:

Secondary index on Name to quickly search “Amit”.

3️⃣ Clustered Index

• Reorders the physical storage of data on disk.

• Only one clustered index allowed per table.

Example:

Employees sorted physically by Department.

4️⃣ Non-Clustered Index

• Does not change physical order of data.

• Stores sorted index information separately.

• Multiple non-clustered indexes can exist per table.

5️⃣ Dense Index

• Index record exists for every record in the data file.

• Fast access but requires more space.

6️⃣ Sparse Index

• Index record exists for some records only.

• Less space but slower compared to dense index.

7️⃣ Multilevel Index

• Large indexes split into multiple levels (like B-trees).

• Improves search speed efficiently.

Structure:

• Level 0 → Actual data

• Level 1 → Index of Level 0

• Level 2 → Index of Level 1

8️⃣ B-Tree and B+ Tree Index

Modern databases mostly use B+ Trees.

B-Tree

• Data stored in internal and leaf nodes.

B+ Tree

• Data stored only in leaf nodes.

• All leaves linked → supports fast range queries.

B+ Trees are preferred because they provide:

• Faster search

• Efficient insertion and deletion

• Balanced height

Dense vs Sparse Index Table

Advantages of Indexing

• Speeds up retrieval operations

• Improves performance of SELECT queries

• Helps in sorting and grouping

• Enhances JOIN performance

• Essential for OLTP systems (banks, airlines, etc.)

Disadvantages of Indexing

• Requires extra memory/storage

• Slows down INSERT, DELETE, and UPDATE operations

• Too many indexes can degrade performance

• Needs regular maintenance (rebuilding)

Conclusion

Indexing is a powerful optimization technique in DBMS used to speed up search and query execution. By creating and maintaining indexes, we avoid full table scans and directly access required records. Modern DBMS systems rely heavily on clustered indexes, non-clustered indexes, and B+ tree structures for achieving high performance, especially in large databases. Proper index selection is vital for efficient database design.