Why storage organization affects query performance in DBMS Theory - Performance Analysis

Time Complexity: Why storage organization affects query performance

O(n) and O(log n)

Understanding Time Complexity

Storage organization impacts how fast a database can find and retrieve data.

We want to know how the way data is stored changes the time it takes to run queries.

Scenario Under Consideration

Analyze the time complexity of the following query on differently organized storage.

SELECT * FROM Employees WHERE EmployeeID = 12345;
    

This query looks for one employee by their ID in the Employees table.

Identify Repeating Operations

Look at how many rows the database must check to find the employee.

• Primary operation: Searching rows for matching EmployeeID
• How many times: Depends on storage type--could be all rows or fewer with indexing

How Execution Grows With Input

If data is stored unordered (heap), the search checks many rows; if indexed, fewer checks are needed.

Input Size (n)	Approx. Operations (Heap Scan)	Approx. Operations (Indexed Search)
10	10 checks	About 4 checks
100	100 checks	About 7 checks
1000	1000 checks	About 10 checks

Pattern observation: Without index, operations grow linearly; with index, growth is much slower.

Final Time Complexity

Time Complexity: O(n) for unordered storage, O(log n) for indexed storage

This means searching takes longer as data grows if storage is unordered, but much less time if data is organized with an index.

Common Mistake

[X] Wrong: "All storage types take the same time to find data because the query is the same."

[OK] Correct: The way data is stored changes how many rows the database must check, so performance differs greatly.

Interview Connect

Understanding how storage affects query speed shows you know how databases work under the hood, a useful skill for real projects.

Self-Check

"What if the Employees table had a clustered index on EmployeeID instead of a non-clustered index? How would the time complexity change?"