Time Complexity: Embedding vs referencing
O(1) for embedding, O(n) for referencing
0
0
Embedding vs referencing in Redis - Performance Comparison
Understanding Time Complexity
When storing a list of related items (like post IDs) in Redis, we can either embed the list as a string in a hash field or store it in a separate set.
We want to see how the time to get data changes as the data grows.
Scenario Under Consideration
Analyze the time complexity of these Redis commands for embedding and referencing.
# Embedding: post IDs as string in hash field
HSET user:1 name "Alice" posts "post1,post2,post3"
# Fetch: O(1)
HGET user:1 posts
# Referencing: post IDs in separate set
HSET user:1 name "Alice"
SADD user:1:posts post1 post2 post3
# Fetch: O(N)
SMEMBERS user:1:posts
This code shows two ways to store and fetch a user's post list: embedded string vs set.
Identify Repeating Operations
Look at what repeats when fetching data.
- Primary operation: HGET for the posts field (embedding) vs SMEMBERS for the posts set (referencing).
- Time growth: Embedding is O(1). Referencing is O(N) where N is the number of posts.
How Execution Grows With Input
As the number of posts grows, the work changes differently for each method.
| Input Size (posts) | Embedding | Referencing |
|---|---|---|
| 10 | O(1) | O(10) |
| 100 | O(1) | O(100) |
| 1000 | O(1) | O(1000) |
Embedding stays constant because all data is fetched at once. Referencing grows linearly with the number of posts.
Final Time Complexity
Time Complexity: O(1) for embedding, O(N) for referencing
Embedding fetches all data in one step, while referencing requires more steps as data grows.
Common Mistake
[X] Wrong: "All single Redis commands are O(1)."
[OK] Correct: SMEMBERS requires time proportional to the set size O(N), unlike HGET which is O(1).
Interview Connect
Understanding how data structure choices affect speed helps you design better Redis solutions and explain your reasoning clearly.
Self-Check
"What if we used a Redis pipeline to fetch all referenced posts at once? How would that affect time complexity?"