Time Complexity: KEYS pattern matching (avoid in production)
O(n)
0
0
KEYS pattern matching (avoid in production) in Redis - Time & Space Complexity
Understanding Time Complexity
When using Redis, the KEYS command helps find keys matching a pattern. But it can be slow if many keys exist.
We want to know how the time to run KEYS grows as the number of keys grows.
Scenario Under Consideration
Analyze the time complexity of the following Redis command.
KEYS user:*
This command finds all keys starting with "user:" by checking every key in the database.
Identify Repeating Operations
Look for repeated work inside the command.
- Primary operation: Scanning every key in the database to check if it matches the pattern.
- How many times: Once for each key stored in Redis.
How Execution Grows With Input
As the number of keys grows, the work grows too because Redis checks each key one by one.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 key checks |
| 100 | About 100 key checks |
| 1000 | About 1000 key checks |
Pattern observation: The time grows directly with the number of keys. Double the keys, double the work.
Final Time Complexity
Time Complexity: O(n)
This means the time to run KEYS grows linearly with the number of keys in the database.
Common Mistake
[X] Wrong: "KEYS is fast even with many keys because Redis is very quick."
[OK] Correct: Redis checks every key one by one, so more keys mean more work and slower response.
Interview Connect
Understanding how commands like KEYS scale helps you write better Redis queries and avoid slowdowns in real projects.
Self-Check
"What if we used SCAN instead of KEYS? How would the time complexity change?"