Time Complexity: RDB snapshots (point-in-time)
O(n)
0
0
RDB snapshots (point-in-time) in Redis - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time to create a Redis RDB snapshot changes as the database grows.
Specifically, how does saving a point-in-time snapshot scale with the amount of data?
Scenario Under Consideration
Analyze the time complexity of this Redis snapshot command.
SAVE
This command creates a point-in-time snapshot of the entire Redis dataset by writing it to disk.
Identify Repeating Operations
What repeats during the snapshot process?
- Primary operation: Iterating over all keys and their values to write them to the snapshot file.
- How many times: Once for each key in the database.
How Execution Grows With Input
As the number of keys grows, the time to save grows too.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 key writes |
| 100 | 100 key writes |
| 1000 | 1000 key writes |
Pattern observation: The time grows roughly in direct proportion to the number of keys.
Final Time Complexity
Time Complexity: O(n)
This means the time to create a snapshot grows linearly with the number of keys in the database.
Common Mistake
[X] Wrong: "Saving a snapshot is instant no matter how much data there is."
[OK] Correct: The snapshot process must visit every key to save it, so more data means more work and more time.
Interview Connect
Understanding how snapshot time grows helps you reason about system performance and data durability in real projects.
Self-Check
"What if Redis used incremental snapshots instead of full snapshots? How would the time complexity change?"