The data structures behind caches, queues and indexes in system design

In a design review last year, someone asked why our leaderboard endpoint got slower as more players joined, even though "it just reads from Redis". The answer was that the code fetched the whole sorted set and sorted it again in the application, turning an O(log n) operation into O(n log n) per request. The fix took ten minutes. Finding it took a day, because nobody was thinking of Redis as a set of data structures with known costs.

Since then we run design reviews with a simple habit: for every component, name the data structure inside it and the cost of the operations we rely on. This post goes through the structures that show up most often in backend systems, with small runnable examples in Python and the questions each one answers during a review.

Big-O as a capacity tool, not an exam topic

Big-O matters in production because it tells you how cost grows as data grows. A constant factor can be tuned; a growth rate cannot.

The jump from 1K to 1M is exactly what happens between staging and a large customer. An O(log n) operation barely notices; an O(n) one gets a thousand times slower.

Hash maps: caches, sessions, deduplication

A hash map gives average O(1) insert, lookup and delete by key. Memcached and Redis strings are distributed hash maps. Idempotency key stores, session stores and request deduplication are all hash maps with an expiry.

What a hash map does not give you is order. Any time a design says "the most recent" or "the oldest" with only a hash map behind it, someone will end up scanning.

LRU cache = hash map + doubly linked list

An LRU cache needs O(1) lookup and O(1) "move to most recent" and "evict least recent". Neither structure alone does both; together they do. Python's OrderedDict combines them internally:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.items: OrderedDict[str, object] = OrderedDict()

    def get(self, key: str):
        if key not in self.items:
            return None
        self.items.move_to_end(key)          # O(1): mark as most recent
        return self.items[key]

    def put(self, key: str, value) -> None:
        self.items[key] = value
        self.items.move_to_end(key)
        if len(self.items) > self.capacity:
            self.items.popitem(last=False)   # O(1): drop least recent

cache = LRUCache(2)
cache.put("a", 1); cache.put("b", 2); cache.get("a"); cache.put("c", 3)
print(list(cache.items))   # ['a', 'c']  -> 'b' was evicted

Redis does not keep an exact LRU list for every key, because the extra pointers per key would cost memory. Its allkeys-lru policy samples a few keys and evicts the oldest of the sample. Knowing this explains why Redis eviction is approximate, and why maxmemory-samples trades CPU for accuracy.

Heaps: priority queues, schedulers and top-K

A binary heap gives O(log n) push and pop of the smallest (or largest) item, and O(1) peek. That is the structure behind job schedulers ("run whatever is due next"), timer wheels in some runtimes, Dijkstra-style routing and delayed retries.

Top-K is the pattern we use most. To find the 10 slowest endpoints out of millions of log lines, sorting everything is O(n log n) and needs all data in memory. A min-heap of size K is O(n log K) with O(K) memory:

import heapq

def slowest(records, k=10):
    heap: list[tuple[float, str]] = []
    for endpoint, latency_ms in records:
        if len(heap) < k:
            heapq.heappush(heap, (latency_ms, endpoint))
        elif latency_ms > heap[0][0]:
            heapq.heapreplace(heap, (latency_ms, endpoint))   # drop current smallest
    return sorted(heap, reverse=True)

data = [("/orders", 120.0), ("/search", 870.5), ("/login", 45.2), ("/export", 2300.0)]
print(slowest(data, k=2))   # [(2300.0, '/export'), (870.5, '/search')]

Delayed job queues in many systems use the same idea with a timestamp as the priority. In Redis that is usually a sorted set rather than a heap, which brings us to ordered structures.

Sorted sets and skip lists: leaderboards, rate limits, delayed jobs

A Redis sorted set keeps members ordered by score. Internally it pairs a hash table (member to score) with a skip list (ordered by score), so it gets O(1) score lookup and O(log n) insert, delete and rank. Range reads cost O(log n + m) for m returned items.

That gives cheap building blocks:

Our leaderboard bug was fetching ZRANGE board 0 -1 and sorting in Python: O(n) transfer plus O(n log n) sort on every request, instead of letting the skip list do the work.

B-trees and LSM trees: database indexes

A B-tree index keeps keys sorted in wide, shallow pages, so a lookup touches only a few pages even for billions of rows: O(log n) with a very large base. Because keys are sorted, the same index serves equality, range and ORDER BY queries, as long as the query uses a leading prefix of the index columns. This is why column order in a composite index matters.

B-trees favour reads. Each insert lands in the right place in the tree, which means random page writes. LSM trees, used by RocksDB, Cassandra and similar stores, buffer writes in memory and flush sorted files sequentially, then merge them in the background. Writes are cheap; reads may have to check several files.

When someone proposes "just add an index", the follow-up question is what it costs on writes and whether the query can actually use it.

Bloom filters: skipping work you do not need to do

A Bloom filter answers "is this key definitely absent, or possibly present?" using a bit array and several hash functions. It never gives a false negative, can give false positives, and uses a few bits per key regardless of key size.

LSM databases keep one per file so a read can skip files that cannot contain the key. We used one in front of a "has this email been seen in a breach list" check, cutting database lookups by over 95%.

import hashlib

class Bloom:
    def __init__(self, size_bits: int, hashes: int):
        self.size, self.k = size_bits, hashes
        self.bits = bytearray(size_bits // 8 + 1)

    def _positions(self, key: str):
        for i in range(self.k):
            h = hashlib.sha256(f"{i}:{key}".encode()).digest()
            yield int.from_bytes(h[:8], "big") % self.size

    def add(self, key: str):
        for p in self._positions(key):
            self.bits[p // 8] |= 1 << (p % 8)

    def might_contain(self, key: str) -> bool:
        return all(self.bits[p // 8] & (1 << (p % 8)) for p in self._positions(key))

b = Bloom(size_bits=10_000, hashes=4)
b.add("user@example.com")
print(b.might_contain("user@example.com"), b.might_contain("other@example.com"))  # True False (almost always)

Hash rings: spreading keys across nodes

Plain hash(key) % N remaps almost every key when N changes, which empties a cache cluster on every scale event. Consistent hashing places nodes on a ring and maps each key to the next node clockwise. Adding a node moves only the keys between it and its predecessor, about 1/N of them.

The implementation is a sorted array plus binary search: O(log V) per lookup, where V is the number of virtual nodes.

import bisect, hashlib

def h(s: str) -> int:
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")

class Ring:
    def __init__(self, nodes, vnodes=100):
        self.points = sorted((h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes))
        self.keys = [p for p, _ in self.points]

    def node_for(self, key: str) -> str:
        i = bisect.bisect(self.keys, h(key)) % len(self.keys)
        return self.points[i][1]

ring = Ring(["cache-a", "cache-b", "cache-c"])
print(ring.node_for("session:9f2c"))

Virtual nodes smooth out the distribution; without them one node can easily own twice its share.

Queues and ring buffers: absorbing bursts

A FIFO queue gives O(1) enqueue and dequeue and turns a burst into a backlog that drains at a steady rate. The data structure question in a review is about its bound. An unbounded in-memory queue converts overload into an out-of-memory crash. A bounded ring buffer (fixed array, head and tail pointers) forces you to decide what happens when it is full: block, drop the oldest, or reject new work.

Common mistakes

Key takeaways

• Name the data structure inside every component; its operation costs are your capacity model.
• Hash maps give O(1) by key but no order; pair them with a list or a tree when order matters.
• Heaps solve "next due" and top-K cheaply; sorted sets add rank and range queries.
• B-trees favour reads and ranges, LSM trees favour writes; pick storage by your read/write mix.
• Bloom filters and hash rings are small ideas that remove whole classes of wasted work and cache misses.

References

• Python heapq documentation: https://docs.python.org/3/library/heapq.html
• Python collections.OrderedDict: https://docs.python.org/3/library/collections.html
• Redis sorted sets: https://redis.io/docs/latest/develop/data-types/sorted-sets/
• Redis key eviction: https://redis.io/docs/latest/develop/reference/eviction/
• PostgreSQL B-tree indexes: https://www.postgresql.org/docs/current/btree.html
• RocksDB wiki, Bloom filter: https://github.com/facebook/rocksdb/wiki/RocksDB-Bloom-Filter