Time Complexity: Why indexing strategy matters
O(log n + k)
0
0
Why indexing strategy matters in PostgreSQL - Performance Analysis
Understanding Time Complexity
When we use indexes in a database, it changes how fast queries run.
We want to see how the choice of indexing affects the time a query takes as data grows.
Scenario Under Consideration
Analyze the time complexity of the following query using an index.
SELECT * FROM employees
WHERE department_id = 5;
This query finds all employees in one department using an index on department_id.
Identify Repeating Operations
Look at what repeats when the query runs.
- Primary operation: Searching the index tree to find matching rows.
- How many times: The search goes down the index levels, which is a few steps regardless of total rows.
How Execution Grows With Input
As the table grows, the index search stays quick, but scanning all rows without an index gets slower.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 3 steps in index + few rows |
| 100 | About 4 steps in index + few rows |
| 1000 | About 5 steps in index + few rows |
Pattern observation: The index search grows very slowly, much better than checking every row.
Final Time Complexity
Time Complexity: O(log n + k)
This means the search time grows slowly with data size, plus time to return matching rows.
Common Mistake
[X] Wrong: "Adding an index always makes queries instantly fast regardless of data or query."
[OK] Correct: Some queries don't use indexes well, and indexes add overhead when writing data.
Interview Connect
Understanding how indexes affect query speed shows you know how databases handle data efficiently.
Self-Check
What if we changed the index to cover multiple columns? How would the time complexity change?