DBMS Notes

Indexing — Introduction

An index is a data structure built on one or more columns of a database table that dramatically speeds up data retrieval operations. It works exactly like...

What is an Index?

An index is a data structure built on one or more columns of a database table that dramatically speeds up data retrieval operations. It works exactly like the index at the back of a textbook — instead of reading every page to find a topic, you look up the topic in the index, find the page number, and jump directly to it.

An index stores a sorted copy of the indexed column values paired with pointers to the actual data rows on disk. When a query filters on an indexed column, the DBMS searches the index (which is small and sorted) instead of scanning the entire table (which may be massive and unsorted).

Index Structure (Conceptual)

001	-> B2		Block 3: E004, E009, E007
002	-> B1		Block 4: E010, E105, E050

The index is much smaller than the data file (it stores only the key + pointer, not the full row), so it fits in fewer blocks and enables efficient search.

Types of Indexes — Classification

Example

Dense vs. Sparse Index

Dense Index

Contains one index entry for every record in the data file.

101	->	------>	Block1: 101, 102
102	->	------>	Block2: 103, 104
103	->	------>	Block3: 105, 106

Sparse Index

Contains one index entry for each disk block (not each record). Only works on sorted (sequential) files.

Sparse Index	Data File (sorted):
\| 101 \| -> \|------> \| Block1	101, 102, 103 \|
\| 104 \| -> \|------> \| Block2	104, 105, 106 \|
\| 107 \| -> \|------> \| Block3	107, 108, 109 \|
To find 105	binary search index -> Block2, then scan within block.

Feature	Dense Index	Sparse Index
Entries	One per record	One per block
Size	Larger	Smaller (fits in memory better)
Lookup speed	Faster (direct pointer)	Slightly slower (block scan needed)
Requirement	Works on any file	Requires sorted data file
Use case	Secondary indexes	Primary indexes on sorted files

Primary, Clustering, and Secondary Indexes

Primary Index

Built on the primary key of a sorted file
Sparse index (one entry per block)
Only ONE primary index per table (since file can be sorted on only one key)

Clustering Index

Built on a non-key ordering field (e.g., department) of a sorted file
One entry per distinct value
Records with same value are clustered in consecutive blocks

Secondary Index

Built on a non-ordering field (file is NOT sorted on this attribute)
Must be dense (one entry per record or per unique value with pointer list)
Multiple secondary indexes can exist per table

Index Trade-offs

Benefit	Cost
Fast SELECT queries	Slower INSERT (must update index too)
Efficient WHERE filtering	Slower UPDATE on indexed columns
Quick ORDER BY on indexed col	Extra disk space for index structure
Faster JOIN operations	Index maintenance overhead

When to Create an Index

Create an index when:

Column is frequently used in WHERE clauses
Column is used in JOIN conditions
Column appears in ORDER BY or GROUP BY
Table is large (thousands+ rows)
Queries are read-heavy

Avoid indexes when:

Table is very small (full scan is just as fast)
Column has very low cardinality (e.g., gender with only 2 values)
Table is write-heavy (constant index updates)
Column is rarely queried

sql example

-- Creating indexes in SQL
CREATE INDEX idx_emp_dept ON Employee(dept_id);
CREATE UNIQUE INDEX idx_emp_email ON Employee(email);
CREATE INDEX idx_orders_date ON Orders(order_date DESC);

-- Composite index (multi-column)
CREATE INDEX idx_name ON Student(last_name, first_name);

Understanding when and how to use indexes is one of the most impactful skills for database performance optimization.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Indexing — Introduction.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Database Management Systems (DBMS) topic.

Search Terms

dbms, database management systems (dbms), unit, indexing, introduction, indexing — introduction

Related Database Management Systems (DBMS) Topics

Continue learning this concept

Unit 5Multi-Level IndexingA single-level index works well when the index itself is small enough to fit in memory. However, as databases grow to millions or billions of records, even...Unit 5Single-Level IndexingA single-level index is a flat index file where each index entry contains a search key value and a pointer to the corresponding data record(s). The index...Unit 5Unit 5 — Storage & IndexingThis unit addresses one of the most critical aspects of database management — how data is physically stored on disk and how it can be retrieved efficiently. While SQL and Unit 5B+ TreeA B+ Tree is a variation of the B-Tree where: - All data records (or pointers to them) are stored only in leaf nodes - Internal nodes store only keys used...Unit 5B-TreeA B-Tree (Balanced Tree) is a self-balancing, sorted tree data structure that maintains sorted data and allows searches, insertions, and deletions in O(log...Unit 5Cost EstimationCost estimation is the process of predicting the execution cost of a query plan without actually running it. The query optimizer uses cost estimates to...

PreviousHashing Techniques NextMulti-Level Indexing