List vs sorted set for sequences in Redis - Performance Comparison

Time Complexity: List vs sorted set for sequences

O(1) for LPUSH, O(k) for LRANGE, O(n) for LREM; O(log n) for ZADD, ZREM, and O(k) for ZRANGE

Understanding Time Complexity

When using Redis to store sequences, it is important to know how fast operations grow as the sequence gets bigger.

We want to see how the time to add, access, or remove items changes with the size of the sequence.

Scenario Under Consideration

Analyze the time complexity of these Redis commands for lists and sorted sets.

# Using a List
LPUSH mylist value
LRANGE mylist 0 9
LREM mylist 1 value

# Using a Sorted Set
ZADD myzset 1 value
ZRANGE myzset 0 9
ZREM myzset value
    

This code adds, reads, and removes items from a list and a sorted set, which are two ways to store sequences in Redis.

Identify Repeating Operations

Look at what repeats when these commands run.

• Primary operation: Adding, reading, and removing items from the data structure.
• How many times: Each command works on the sequence size, which can be many items.

How Execution Grows With Input

As the sequence grows, the time to do these operations changes differently for lists and sorted sets.

Input Size (n)	List Operations	Sorted Set Operations
10	Fast for push and range, slow for remove	Fast for add, range, and remove
100	Push and range still fast, remove slower	All operations remain efficient
1000	Remove becomes noticeably slower	Operations scale well

Lists are quick to add and read from the start but removing items can take longer as the list grows. Sorted sets keep operations fast even as size grows.

Final Time Complexity

Time Complexity: O(1) for LPUSH, O(k) for LRANGE, O(n) for LREM; O(log n) for ZADD, ZREM, and O(k) for ZRANGE

This means lists are very fast to add at the front and read ranges, but removing items can take longer as the list grows. Sorted sets keep add, remove, and range operations efficient even with large sequences.

Common Mistake

[X] Wrong: "Lists and sorted sets have the same speed for all operations because they both store sequences."

[OK] Correct: Lists are simple sequences with fast push/pop at ends but slow removal inside. Sorted sets use a tree structure that keeps operations like add and remove faster even as size grows.

Interview Connect

Understanding how Redis data structures behave as data grows shows you can choose the right tool for the job. This skill helps you design fast and scalable systems.

Self-Check

What if we changed the sorted set scores to be random instead of ordered? How would that affect the time complexity of range queries?

Practice

1. Which Redis data structure allows storing duplicate elements while preserving their order?

easy

A. Hash

B. List

C. Sorted Set

D. Set

Solution

1. Step 1: Understand List behavior

   Lists in Redis keep elements in the order they were added and allow duplicates.

2. Step 2: Compare with Sorted Set

   Sorted sets store unique elements sorted by score, so duplicates are not allowed.

3. Final Answer:

   List -> Option B

4. Quick Check:

   Duplicates allowed and order preserved = List [OK]

Hint: Duplicates allowed? Use List, not Sorted Set. [OK]

Common Mistakes:

• Thinking Sorted Set allows duplicates
• Confusing Sets with Lists
• Assuming Hashes store sequences

2. Which of the following Redis commands correctly adds an element with a score to a sorted set?

easy

A. HSET myhash field element

B. LPUSH mylist element

C. SADD myset element

D. ZADD myzset 10 element

Solution

1. Step 1: Identify command for sorted set insertion

   ZADD adds elements with a score to a sorted set.

2. Step 2: Check other commands

   LPUSH adds to list, SADD adds to set, HSET adds to hash field.

3. Final Answer:

   ZADD myzset 10 element -> Option D

4. Quick Check:

   ZADD = add with score [OK]

Hint: ZADD is for sorted sets with scores. [OK]

Common Mistakes:

• Using LPUSH for sorted sets
• Confusing SADD with ZADD
• Using HSET for sequences

3. Given the following Redis commands executed in order:
LPUSH mylist a
LPUSH mylist b
LPUSH mylist c
What will LRANGE mylist 0 -1 return?

medium

A. ["a", "b", "c"]

B. ["b", "c", "a"]

C. ["c", "b", "a"]

D. Error

Solution

1. Step 1: Understand LPUSH order

   LPUSH adds elements to the head (start) of the list, so last pushed is first.

2. Step 2: Trace the list after pushes

   LPUSH mylist a: ["a"], then LPUSH mylist b: ["b", "a"], then LPUSH mylist c: ["c", "b", "a"]. LRANGE mylist 0 -1 returns ["c", "b", "a"].

3. Final Answer:

   ["c", "b", "a"] -> Option C

4. Quick Check:

   LPUSH adds to head, so newest first [OK]

Hint: LPUSH adds to front; last pushed appears first. [OK]

Common Mistakes:

• Assuming LPUSH adds to tail
• Mixing order of elements
• Expecting error from LRANGE

4. You tried to add duplicate elements with different scores to a sorted set using:
ZADD myzset 1 element
ZADD myzset NX 2 element
But the score did not update as expected. What is the likely issue?

medium

A. Sorted sets do not allow duplicate elements; score updates require special flag

B. ZADD command syntax is incorrect

C. You must remove the element before adding it again

D. Redis lists should be used instead

Solution

1. Step 1: Understand sorted set uniqueness

   Sorted sets store unique elements; adding the same element updates its score by default.

2. Step 2: Check if score updates require flags

   By default, ZADD updates score if element exists; if it did not update, likely a misunderstanding or missing flag like NX or XX.

3. Final Answer:

   Sorted sets do not allow duplicate elements; score updates require special flag -> Option A

4. Quick Check:

   Sorted sets unique, score updates need care [OK]

Hint: Sorted sets unique; score updates may need flags. [OK]

Common Mistakes:

• Thinking duplicates allowed in sorted sets
• Assuming ZADD syntax is wrong
• Trying to remove before adding

5. You want to store a sequence of user actions with timestamps and retrieve them sorted by time, allowing multiple actions at the same timestamp. Which Redis data structure and approach is best?

hard

A. Use a Sorted Set with timestamps as scores; append a unique suffix to actions to allow duplicates

B. Use a List and store actions with timestamps as strings; order is insertion order

C. Use a Hash with timestamps as fields and actions as values

D. Use a Set to store actions; order does not matter

Solution

1. Step 1: Analyze requirement for sorting by timestamp

   Sorted sets sort elements by numeric score, perfect for timestamps.

2. Step 2: Handle duplicates with same timestamp

   Sorted sets require unique elements, so append unique suffix to actions to allow duplicates with same score.

3. Step 3: Compare with other options

   Lists preserve order but cannot sort by timestamp easily; hashes and sets do not maintain order or allow sorting by score.

4. Final Answer:

   Use a Sorted Set with timestamps as scores; append a unique suffix to actions to allow duplicates -> Option A

5. Quick Check:

   Sorted set + unique elements for timestamp sorting [OK]

Hint: Sorted set + unique suffix for duplicates with same score. [OK]

Common Mistakes:

• Using List but losing timestamp sorting
• Ignoring uniqueness in sorted sets
• Using Hash or Set which don't sort