Index selection guidelines in DBMS Theory - Time & Space Complexity

Time Complexity: Index selection guidelines

O(n) without index, O(log n) with index

Understanding Time Complexity

Choosing the right index affects how fast a database finds data.

We want to know how the time to find data changes as the data grows.

Scenario Under Consideration

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

-- Without index
SELECT * FROM employees WHERE employee_id = 12345;

-- With index on employee_id
CREATE INDEX idx_employee_id ON employees(employee_id);
SELECT * FROM employees WHERE employee_id = 12345;
    

This code shows a search query before and after adding an index on the searched column.

Identify Repeating Operations

Look at what repeats when searching for data.

• Primary operation: Scanning rows to find matching employee_id.
• How many times: Without index, it checks each row one by one; with index, it uses a tree to jump directly.

How Execution Grows With Input

As the table grows, the search time changes differently with and without an index.

Input Size (n)	Approx. Operations Without Index
10	10 checks
100	100 checks
1000	1000 checks

Input Size (n)	Approx. Operations With Index
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: Without index, operations grow directly with data size; with index, operations grow slowly as data grows.

Final Time Complexity

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

This means searching without an index gets slower as data grows, but with an index it stays much faster.

Common Mistake

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

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

Interview Connect

Understanding how indexes affect search time helps you explain database speed choices clearly and confidently.

Self-Check

"What if we added a composite index on two columns instead of one? How would the time complexity change?"