Time Complexity: Bitmap indexes
O(n)
0
0
Bitmap indexes in DBMS Theory - Time & Space Complexity
Understanding Time Complexity
Bitmap indexes help speed up searching in databases by using bits to represent data presence.
We want to understand how the time to search grows as the data size increases.
Scenario Under Consideration
Analyze the time complexity of using a bitmap index to find rows matching a condition.
-- Assume a bitmap index on a column with distinct values
SELECT ROWID FROM table WHERE bitmap_index & condition_bitmap = condition_bitmap;
This code uses bitwise AND on bitmap indexes to quickly find matching rows.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Bitwise AND on bitmap segments representing rows.
- How many times: Once per bitmap segment, which covers many rows at once.
How Execution Grows With Input
As the number of rows grows, the bitmap size grows proportionally, so more bits must be processed.
| Input Size (n rows) | Approx. Operations (bitwise checks) |
|---|---|
| 10 | 10 bits processed |
| 100 | 100 bits processed |
| 1000 | 1000 bits processed |
Pattern observation: The work grows linearly with the number of rows because each row corresponds to one bit.
Final Time Complexity
Time Complexity: O(n)
This means the time to search grows directly in proportion to the number of rows in the table.
Common Mistake
[X] Wrong: "Bitmap indexes always give constant time search regardless of data size."
[OK] Correct: Even though bit operations are fast, the bitmap size grows with data, so more bits must be checked as data grows.
Interview Connect
Understanding how bitmap indexes scale helps you explain database search efficiency clearly and confidently.
Self-Check
What if the bitmap index was compressed? How would that affect the time complexity?