Memory-efficient data structures in Redis - Time & Space Complexity

Time Complexity: Memory-efficient data structures

O(n)

Understanding Time Complexity

When using memory-efficient data structures in Redis, it's important to understand how the time to access or modify data changes as the data grows.

We want to know how the speed of operations changes when we store more items in these structures.

Scenario Under Consideration

Analyze the time complexity of accessing elements by index in a Redis ziplist.

# Create a ziplist and add elements
RPUSH mylist item1
RPUSH mylist item2
RPUSH mylist item3

# Access element by index
LINDEX mylist 1

# Add another element
RPUSH mylist item4

This code adds items to a memory-efficient list called a ziplist and accesses an element by its position.

Identify Repeating Operations

Look at what repeats when we access items.

• Primary operation: Traversing the ziplist to find the element or position.
• How many times: Depends on the index or position in the list; it may scan through elements one by one.

How Execution Grows With Input

As the list grows, finding an element by index takes longer because Redis scans through items.

Input Size (n)	Approx. Operations
10	About 5 steps to find middle item
100	About 50 steps to find middle item
1000	About 500 steps to find middle item

Pattern observation: The number of steps grows roughly in proportion to the position searched, so bigger lists take longer to access items in the middle.

Final Time Complexity

Time Complexity: O(n)

This means the time to access an element by index grows linearly with the number of items in the list.

Common Mistake

[X] Wrong: "Accessing any element in a ziplist is instant, no matter how big it is."

[OK] Correct: Because ziplists store items compactly, Redis must scan through elements to find the right one, so bigger lists take more time.

Interview Connect

Understanding how memory-efficient structures affect speed helps you explain trade-offs clearly, a skill valuable in real projects and interviews.

Self-Check

"What if we replaced the ziplist with a Redis list data structure? How would the time complexity for accessing elements change?"

Practice

1. Which Redis data structure is best suited for storing many small key-value pairs efficiently in memory?

easy

A. List

B. Set

C. Hash

D. String

Solution

1. Step 1: Understand Redis data structures

   Hashes store multiple field-value pairs under one key, saving memory compared to many separate keys.

2. Step 2: Compare with other structures

   Lists and sets store collections but are less memory-efficient for many small pairs; strings store single values only.

3. Final Answer:

   Hash -> Option C

4. Quick Check:

   Hashes = memory-efficient key-value pairs [OK]

Hint: Use hashes for many small key-value pairs to save memory [OK]

Common Mistakes:

• Choosing List or Set for key-value pairs
• Thinking String can store multiple pairs
• Ignoring memory efficiency of Hashes

2. Which of the following is the correct Redis command to add a field-value pair to a hash named user:1?

easy

A. HSET user:1 name "Alice"

B. SADD user:1 name "Alice"

C. LPUSH user:1 name "Alice"

D. SET user:1 name "Alice"

Solution

1. Step 1: Identify the command for hashes

   HSET adds or updates a field in a hash key in Redis.

2. Step 2: Check other commands

   SADD is for sets, LPUSH for lists, SET for strings; none add fields to hashes.

3. Final Answer:

   HSET user:1 name "Alice" -> Option A

4. Quick Check:

   HSET = add field to hash [OK]

Hint: Use HSET to add fields to hashes in Redis [OK]

Common Mistakes:

• Using SADD or LPUSH for hashes
• Confusing SET with HSET
• Incorrect command syntax

3. Given the Redis commands:
HSET user:2 age 30
HSET user:2 city "NYC"
What will HGETALL user:2 return?

medium

A. ["age", "30", "city", "NYC"]

B. ["user:2", "age", "30", "city", "NYC"]

C. ["age", 30, "city", "NYC"]

D. ["age", "30", "city"]

Solution

1. Step 1: Understand HSET commands

   Two fields, 'age' and 'city', are set with values '30' and 'NYC' in hash 'user:2'.

2. Step 2: Check HGETALL output format

   HGETALL returns a flat list of field-value pairs as strings.

3. Final Answer:

   ["age", "30", "city", "NYC"] -> Option A

4. Quick Check:

   HGETALL returns field-value pairs list [OK]

Hint: HGETALL returns flat list of fields and values [OK]

Common Mistakes:

• Expecting key name in output
• Mixing data types (string vs integer)
• Missing value for a field

4. You run the command HSET user:3 name "Bob" but get an error. Which is the most likely cause?

medium

A. Redis does not support hashes with string fields

B. The key user:3 already holds a string value

C. HSET requires a numeric field value

D. The field name is reserved and cannot be used

Solution

1. Step 1: Understand Redis type errors

   If the key 'user:3' holds a string, trying to use HSET (hash command) causes a type error.

2. Step 2: Check other options

   Field names are not reserved, HSET accepts strings, and Redis supports string fields in hashes.

3. Final Answer:

   The key user:3 already holds a string value -> Option B

4. Quick Check:

   Type mismatch causes HSET error [OK]

Hint: Check key type before using hash commands [OK]

Common Mistakes:

• Assuming field names are restricted
• Thinking HSET needs numeric values
• Ignoring Redis data type rules

5. You want to store user preferences with many optional fields but minimize memory. Which Redis approach is best?

hard

A. Use a set with all field names as members

B. Use a list with all possible fields and empty strings for missing

C. Use separate string keys for each field

D. Use a hash with only fields that have values

Solution

1. Step 1: Consider memory efficiency

   Hashes store only existing fields, saving memory by omitting empty or missing fields.

2. Step 2: Evaluate other options

   Lists with empty strings waste memory; sets store unique members but not key-value pairs; separate keys increase overhead.

3. Final Answer:

   Use a hash with only fields that have values -> Option D

4. Quick Check:

   Hashes save memory by storing only present fields [OK]

Hint: Store only present fields in hashes to save memory [OK]

Common Mistakes:

• Using lists with empty placeholders
• Using sets for key-value data
• Creating many separate keys