Key design patterns in Redis - Time & Space Complexity

Time Complexity: Key design patterns

O(n)

Understanding Time Complexity

When using Redis key design patterns, it is important to understand how the time to access or modify keys changes as the number of keys grows.

We want to know how the operations scale when we use common patterns like namespaces or key prefixes.

Scenario Under Consideration

Analyze the time complexity of accessing keys with a common prefix pattern.

# Set keys with a prefix
SET user:1001 "Alice"
SET user:1002 "Bob"
SET user:1003 "Carol"

# Retrieve keys by prefix
KEYS user:*
    

This code sets several keys with the prefix "user:" and then retrieves all keys starting with that prefix.

Identify Repeating Operations

Look for operations that repeat or scan through data.

• Primary operation: The KEYS command scans all keys to find matches.
• How many times: It checks every key in the database once.

How Execution Grows With Input

As the number of keys grows, the time to run KEYS user:* grows too.

Input Size (n)	Approx. Operations
10	10 key checks
100	100 key checks
1000	1000 key checks

Pattern observation: The number of operations grows directly with the number of keys.

Final Time Complexity

Time Complexity: O(n)

This means the time to find keys with a prefix grows linearly as the total number of keys increases.

Common Mistake

[X] Wrong: "Using key prefixes makes key searches instant regardless of database size."

[OK] Correct: The KEYS command still scans all keys, so the time depends on total keys, not just the prefix.

Interview Connect

Understanding how key patterns affect performance helps you design efficient Redis databases and answer questions about scaling data access.

Self-Check

"What if we replaced KEYS with SCAN for prefix matching? How would the time complexity change?"