Indexing in DBMS
Subject: Computer Science Fundamentals · Language: DBMS · Level: beginner · 10 min read
Learn indexing in DBMS with beginner-friendly explanation of index types, primary and secondary indexes, dense and sparse indexes, B+ tree idea, and when indexes help.
Indexing is a technique used by a DBMS to find records faster. When a table contains only a few rows, searching row by row may feel fine. But when a table contains thousands, lakhs, or millions of rows, checking every row becomes slow.
An index works like the index page of a book. If you want to find a topic in a large book, you do not read every page from the beginning. You check the index, find the page number, and directly go near the required content. A database index follows a similar idea.
A beginner should remember one simple point: an index does not change the actual table data. It creates an additional search structure that helps the DBMS locate rows quickly.
Why Indexing Is Needed
Without an index, the DBMS may need to perform a full table scan. A full table scan means checking rows one by one until the required record is found. This can be expensive when the table is large.
For example, if a Students table has one million rows and we search by roll number, scanning all rows is wasteful. If roll number has an index, the DBMS can use that index to reach the required row much faster.
Indexes are important in search-heavy systems such as college portals, banking systems, ecommerce websites, library systems, hospital systems, and admin dashboards.
Simple Index Diagram
This diagram shows the basic idea of an index.
```text
Index on roll_no
+---------+----------------+
| roll_no | row_location |
+---------+----------------+
| 101 | Row address A |
| 102 | Row address B |
| 103 | Row address C |
+---------+----------------+
Students table
Row address A -> Rahul's full record
Row address B -> Priya's full record
Row address C -> Aman's full record
```
The index stores the search value and a pointer or reference to the actual row. The DBMS first searches the index, then uses the stored location to fetch the full record.
How an Index Helps
Suppose we run this query.
```sql
SELECT * FROM Students
WHERE roll_no = 102;
```
If there is no index on `roll_no`, the DBMS may check every row until it finds roll number 102. If there is an index on `roll_no`, the DBMS can search the index structure and directly locate the row.
This makes read operations faster, especially when the condition uses indexed columns.
Types of Indexes
Important index types are listed below.
1. Primary index: Created on a primary key or ordering key of a sorted file.
2. Secondary index: Created on a non-ordering column to improve search.
3. Clustered index: Decides or follows the physical order of data rows.
4. Non-clustered index: Stores a separate structure pointing to actual rows.
5. Dense index: Contains an index entry for every search key value.
6. Sparse index: Contains index entries for only some search key values.
7. Single-level index: Uses one index level.
8. Multi-level index: Uses indexes over indexes for faster search in large data.
9. Composite index: Created using more than one column.
10. Unique index: Ensures indexed values do not repeat.
These names may look many at first, but they become easier when we connect them with purpose. Some indexes are based on table order, some are based on how many entries they store, and some are based on how many columns they use.
Primary Index
A primary index is usually built on a primary key or a key field that uniquely identifies records. If the data file is sorted according to that key, the index can help locate records efficiently.
For example, if Students are stored in order of `roll_no`, a primary index on `roll_no` can quickly guide the DBMS to the required section of the table.
Primary indexes are useful because primary key values are unique. Searching with a unique key usually returns at most one row, so the DBMS can stop searching once the row is found.
Secondary Index
A secondary index is created on a column that is not necessarily the main ordering key. It is useful when users frequently search by that column.
For example, the Students table may be stored by roll number, but users may often search by department. In that case, a secondary index on `department` can help.
A secondary index may point to multiple rows because many students can belong to the same department.
```sql
CREATE INDEX idx_students_department
ON Students(department);
```
After this index is created, queries filtering by department may become faster.
Clustered Index
A clustered index is connected with the physical order of rows. In simple words, the actual table data is stored in the same order as the clustered index.
For example, if a table has a clustered index on roll number, the rows may be physically arranged according to roll number. This can make range queries faster.
```sql
SELECT * FROM Students
WHERE roll_no BETWEEN 100 AND 150;
```
Since nearby roll numbers are stored close to each other, the DBMS can read the range more efficiently.
A table usually has only one clustered index because physical order can follow only one main arrangement.
Non-Clustered Index
A non-clustered index is a separate structure from the actual table data. It stores indexed values and pointers to the real rows.
For example, a table may be physically ordered by roll number, but it can still have a non-clustered index on name or department. The index helps find matching row locations.
A table can have multiple non-clustered indexes. However, each extra index needs storage and maintenance.
Dense Index
A dense index has an index entry for every search key value. If every student roll number appears in the index, it is dense.
Dense indexes make searching direct because the required key is expected to appear in the index. But they may take more storage because many entries are stored.
Dense indexing is easy to understand because every searchable value has a clear entry.
Sparse Index
A sparse index stores entries for only some search key values. It is usually used when data is sorted.
The DBMS first uses the sparse index to reach a block or range, then searches inside that smaller section. This uses less storage than dense indexing, but it may require a little extra searching inside the selected block.
Sparse indexes are useful when index size should be smaller and data ordering makes block-level searching possible.
Dense Index vs Sparse Index
This table compares dense and sparse indexes.
| Point | Dense Index | Sparse Index |
| --- | --- | --- |
| Entries | Entry for every search key value | Entry for selected search key values |
| Storage | Needs more storage | Needs less storage |
| Search | More direct | First reaches a range, then searches inside it |
| Requirement | Can work without sorted data | Usually needs sorted data |
| Example | Every roll number appears in index | First roll number of each block appears in index |
Dense index is easier for direct lookup. Sparse index is more space-efficient when data is sorted and organized into blocks.
Multi-Level Index
When an index itself becomes large, searching the index may also take time. A multi-level index solves this by creating an index on top of another index.
This is similar to a book having chapter headings, then section headings, then page details. Instead of scanning a large index directly, the DBMS uses higher-level indexes to narrow the search.
```text
Top-level index
|
v
Second-level index
|
v
Data-level index
|
v
Actual table rows
```
Multi-level indexing is useful in large databases because it keeps search efficient even when the amount of data grows.
B Tree and B Plus Tree Idea
Many database systems use tree-based indexes such as B Tree or B Plus Tree. These structures keep keys sorted and balanced so searching, insertion, and deletion remain efficient.
In a B Plus Tree, actual data pointers are usually stored at leaf nodes, and leaf nodes are linked together. This helps both exact search and range search.
A beginner does not need to implement B Plus Tree immediately, but should understand why databases use it: it keeps search fast even for very large tables.
Composite Index
A composite index is created using more than one column.
```sql
CREATE INDEX idx_students_dept_marks
ON Students(department, marks);
```
This index can help queries that filter by department and marks together.
```sql
SELECT * FROM Students
WHERE department = 'CSE' AND marks >= 80;
```
Column order matters in composite indexes. An index on `(department, marks)` is not always the same as an index on `(marks, department)` because the DBMS uses the leftmost column order while searching.
Advantages of Indexing
Indexes make search queries faster. They are especially helpful for columns used often in `WHERE`, `JOIN`, `ORDER BY`, and `GROUP BY` clauses.
They can also improve sorting and joining performance because the DBMS may use the index order instead of sorting everything from scratch.
In large applications, correct indexing can make the difference between a slow page and a fast page.
Disadvantages of Indexing
Indexes are not free. They take extra storage because the DBMS must store the index structure separately.
They can also slow down insert, update, and delete operations. Whenever table data changes, related indexes may also need to be updated.
This is why we should not create indexes blindly on every column. Too many indexes can make write operations slow and waste storage.
When to Create an Index
Create indexes on columns that are searched frequently, used in joins, used for sorting, or used for grouping. Primary keys and foreign keys are common candidates.
Avoid indexes on columns that change very frequently, columns with very few distinct values, or small tables where scanning is already fast.
For example, indexing gender in a small table may not help much because there are very few distinct values. Indexing roll number, email, order ID, or account number is usually more useful.
Important Points to Remember
Indexing improves read performance by helping the DBMS find rows faster. It creates an additional search structure and does not replace the table itself.
Indexes are useful, but they need storage and maintenance. They should be created based on query needs, not simply because indexing sounds good.
For interviews, remember primary index, secondary index, clustered index, non-clustered index, dense index, sparse index, composite index, and the basic B Plus Tree idea.