Why indexing speeds up data retrieval in DBMS Theory - Performance Analysis

Time Complexity: Why indexing speeds up data retrieval

O(log n)

Understanding Time Complexity

When we search for data in a database, the time it takes can change a lot depending on how the data is organized.

We want to understand how using an index changes the speed of finding data.

Scenario Under Consideration

Analyze the time complexity of searching data with and without an index.

-- Without index: full table scan
SELECT * FROM Employees WHERE EmployeeID = 12345;

-- With index on EmployeeID
CREATE INDEX idx_employeeid ON Employees(EmployeeID);
SELECT * FROM Employees WHERE EmployeeID = 12345;

The first query searches the whole table, the second uses an index to find the data faster.

Identify Repeating Operations

Look at what repeats when searching:

• Primary operation without index: Checking each row one by one.
• How many times: Once for every row in the table.
• Primary operation with index: Navigating the index tree to find the matching entry.
• How many times: A few steps, much less than total rows.

How Execution Grows With Input

Imagine the table grows bigger:

Input Size (n)	Approx. Operations Without Index	Approx. Operations With Index
10	10 checks	About 3 steps
100	100 checks	About 4 steps
1000	1000 checks	About 5 steps

Without an index, the work grows directly with the number of rows. With an index, the steps grow slowly, even if the table gets very large.

Final Time Complexity

Time Complexity: O(n) without index, O(log n) with index

This means searching without an index takes longer as the table grows, but with an index, it stays fast even for big tables.

Common Mistake

[X] Wrong: "Adding an index always makes every query faster."

[OK] Correct: Indexes speed up searches but can slow down data changes like inserts or updates because the index must be updated too.

Interview Connect

Understanding how indexes affect search speed shows you know how databases handle data efficiently, a useful skill for many real-world projects.

Self-Check

"What if the index was on a column with many repeated values instead of unique ones? How would the time complexity change?"