Primary vs secondary indexes in DBMS Theory - Performance Comparison

Time Complexity: Primary vs secondary indexes

O(log n)

Understanding Time Complexity

Indexes help databases find data faster. We want to understand how using primary or secondary indexes affects the time it takes to search.

How does the choice of index change the work done as data grows?

Scenario Under Consideration

Analyze the time complexity of searching with primary and secondary indexes.

-- Searching with Primary Index
SELECT * FROM Employees WHERE EmployeeID = 12345;

-- Searching with Secondary Index
SELECT * FROM Employees WHERE Department = 'Sales';
    

The first query uses a primary index on EmployeeID, the second uses a secondary index on Department.

Identify Repeating Operations

Look at what repeats when searching:

• Primary index search: Uses a tree or sorted structure to find one record quickly.
• Secondary index search: Finds all matching records, may need extra steps to get full data.
• Dominant operation: Number of lookups in the index and data retrieval steps.

How Execution Grows With Input

As the number of records (n) grows, the work changes:

Input Size (n)	Primary Index Lookups	Secondary Index Lookups
10	About 3 steps	About 3 steps + fetching multiple rows
100	About 7 steps	About 7 steps + fetching multiple rows
1000	About 10 steps	About 10 steps + fetching multiple rows

Primary index search grows slowly with data size. Secondary index search also grows slowly for lookup but may fetch many rows, increasing work.

Final Time Complexity

Time Complexity: O(log n) for primary index search, O(log n + k) for secondary index search where k is matching rows.

This means finding one record by primary index is fast and grows slowly, but secondary index search can take longer if many records match.

Common Mistake

[X] Wrong: "Secondary indexes are always as fast as primary indexes."

[OK] Correct: Secondary indexes may return many records, so fetching all data can take more time than a single primary key lookup.

Interview Connect

Understanding how indexes affect search speed shows you know how databases handle data efficiently. This helps you explain choices in real projects clearly.

Self-Check

"What if the secondary index is on a unique column? How would the time complexity change?"