Time Complexity: ZRANGEBYSCORE for score-based queries
O(log n + m)
0
0
ZRANGEBYSCORE for score-based queries in Redis - Time & Space Complexity
Understanding Time Complexity
When we use ZRANGEBYSCORE in Redis, we want to find items within a score range quickly.
We ask: How does the time to get these items grow as the data grows?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
# Get all members with scores between 50 and 100
ZRANGEBYSCORE mysortedset 50 100
# Optionally limit results
ZRANGEBYSCORE mysortedset 50 100 LIMIT 0 10
This code fetches members from a sorted set whose scores fall between 50 and 100, optionally limiting the number of results.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Scanning the sorted set to find members in the score range.
- How many times: Depends on how many members fall within the score range; Redis uses a skiplist to jump quickly.
How Execution Grows With Input
As the sorted set grows, finding the start point is fast, but returning more results takes more time.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 3 to 5 steps to find start, plus up to 10 to return |
| 100 | About 5 to 7 steps to find start, plus up to 100 to return |
| 1000 | About 7 to 10 steps to find start, plus up to 1000 to return |
Pattern observation: Finding where to start grows slowly, but returning more results grows linearly with how many are returned.
Final Time Complexity
Time Complexity: O(log n + m)
This means it takes a small amount of time to find where to start, plus time proportional to how many results you get back.
Common Mistake
[X] Wrong: "ZRANGEBYSCORE always takes the same time no matter how many results it returns."
[OK] Correct: The time to find the start is fast, but returning many results takes longer because Redis must send each member back.
Interview Connect
Understanding how Redis handles score-based queries helps you explain efficient data retrieval in real systems.
Self-Check
"What if we add a LIMIT clause to always return only 5 results? How would the time complexity change?"