Stream entry IDs in Redis - Time & Space Complexity

Time Complexity: Stream entry IDs

O(1) for adding, O(k) for reading k entries

Understanding Time Complexity

We want to understand how the time to process stream entry IDs in Redis grows as the number of entries increases.

Specifically, how does Redis handle entry IDs when adding or reading from streams?

Scenario Under Consideration

Analyze the time complexity of adding entries to a Redis stream and reading entries by ID.

XADD mystream * field1 value1
XADD mystream * field2 value2
XRANGE mystream 0-0 +
XREAD COUNT 10 STREAMS mystream 0-0
    

This code adds entries with auto-generated IDs to a stream and reads entries by ID range or count.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Adding entries and scanning entries by ID range.
• How many times: Each XADD adds one entry; XRANGE or XREAD may scan multiple entries depending on count.

How Execution Grows With Input

As the number of entries grows, adding one entry stays quick, but reading more entries takes longer.

Input Size (n)	Approx. Operations
10	Adding: 1 operation, Reading: up to 10 operations
100	Adding: 1 operation, Reading: up to 100 operations
1000	Adding: 1 operation, Reading: up to 1000 operations

Pattern observation: Adding an entry is constant time; reading scales with how many entries you request.

Final Time Complexity

Time Complexity: O(1) for adding entries, O(k) for reading k entries.

This means adding one entry takes the same time no matter how big the stream is, but reading depends on how many entries you want.

Common Mistake

[X] Wrong: "Adding entries to a Redis stream gets slower as the stream grows because it has to check all previous entries."

[OK] Correct: Redis uses efficient internal structures so adding an entry is quick and does not scan the whole stream.

Interview Connect

Understanding how Redis handles stream entry IDs helps you explain performance in real-time data systems, showing you know how data size affects speed.

Self-Check

What if we changed reading entries by ID range to reading entries by a filtered field value? How would the time complexity change?