Dense vs sparse indexes in DBMS Theory - Performance Comparison

Time Complexity: Dense vs sparse indexes

O(log n)

Understanding Time Complexity

When using indexes in databases, it is important to understand how quickly they help find data as the database grows.

We want to know how the time to search changes with dense and sparse indexes.

Scenario Under Consideration

Analyze the time complexity of searching using dense and sparse indexes.

-- Dense index: one index entry per record
SELECT record FROM data_table WHERE key = search_key; -- using dense index

-- Sparse index: one index entry per block of records
SELECT record FROM data_table WHERE key = search_key; -- using sparse index

This code shows searching for a record using either a dense or sparse index in a database.

Identify Repeating Operations

Look at what repeats when searching with each index type.

• Primary operation: Searching through index entries to find the correct record or block.
• How many times: For dense index, one entry per record; for sparse index, one entry per block of records.

How Execution Grows With Input

As the number of records grows, the number of index entries grows differently for dense and sparse indexes.

Input Size (n)	Dense Index Entries	Sparse Index Entries
10	10	2 (assuming 5 records per block)
100	100	20
1000	1000	200

Pattern observation: Dense index entries grow directly with the number of records, while sparse index entries grow slower because they index blocks.

Final Time Complexity

Time Complexity: O(log n)

This means searching using either index grows slowly and efficiently as the database size increases.

Common Mistake

[X] Wrong: "Sparse indexes always make searching slower because they have fewer entries."

[OK] Correct: Sparse indexes reduce the number of index entries, but searching still uses efficient methods like binary search, so the time grows slowly.

Interview Connect

Understanding how dense and sparse indexes affect search time helps you explain database performance clearly and confidently in real-world discussions.

Self-Check

"What if the sparse index indexed every 10th record instead of every block? How would that change the time complexity?"