Production Case Study: Redis ZSET (Listpack vs SkipList + Dict Dual Indexing)

Dual-Indexing Architecture: Why Redis Combines a Hash Table + Augmented Skip List

Consider the API contract of a Redis Sorted Set (ZSET, implemented in src/t_zset.c by Salvatore Sanfilippo): every element is a unique string ele paired with a 64-bit IEEE-754 floating-point double score, ordered primarily by score ascending and secondarily by lexicographical ele ascending. Look at the conflicting access patterns required:

• ZSCORE key member asks: "What is the score of member $X$?" A pure Skip List or B-Tree ordered by (score, ele) cannot search by ele alone without scanning all $N$ nodes in $O(N)$ time!
• ZRANGEBYSCORE key min max asks: "Return all members with score $\in [\text{min}, \text{max}]$." A hash table keyed by ele cannot answer ordered range queries without an $O(N \log N)$ sort!
• ZRANK key member and ZRANGE key 100 150 ask: "What is the 0-based positional index of member $X$?" and "Return the 100th through 150th elements."

Redis solves all three simultaneously inside struct zset by composing two structures that share the exact same underlying string allocations (sds):

1. A Hash Table (dict *dict): Maps ele -> score in $O(1)$ time.
2. An Order-Statistic Skip List (zskiplist *zsl): Indexes (score, ele) in sorted order, augmented with level span counters and a level-0 backward pointer.

Adaptive Representation: Small OBJ_ENCODING_LISTPACK vs. Large OBJ_ENCODING_SKIPLIST

Visualizing Redis zskiplistNode Layout & span Rank Accumulation

Redis ZSET Command Dispatch & Encoding Promotion Flow

Production Implementation: Order-Statistic Skip List Node with rank & get_by_rank

#include <array>
#include <cstddef>
#include <cstdint>
#include <string>

// Simplified Redis-style Order-Statistic Skip List supporting O(log N) Rank & Select
class RankedSkipList {
  static constexpr int MAX_LEVEL = 16;

  struct LevelLink {
    int next_idx = 0;       // 0 = nullptr sentinel
    std::size_t span = 0;   // Number of level-0 nodes skipped by this link
  };

  struct Node {
    double score = 0.0;
    int member_id = 0;
    int backward = 0;
    std::array<LevelLink, MAX_LEVEL> level{};
  };

  std::array<Node, 4096> pool_{}; // Contiguous pool; index 0 is head sentinel
  int pool_used_ = 1;
  int max_lvl_ = 1;

  static bool less_than(double s1, int m1, double s2, int m2) noexcept {
    return (s1 < s2) || (s1 == s2 && m1 < m2);
  }

public:
  // O(log N) ZRANK: Returns 1-based rank of (score, member_id), or 0 if not found
  std::size_t get_rank(double score, int member_id) const noexcept {
    std::size_t rank = 0;
    int x = 0; // Start at head (index 0)
    for (int i = max_lvl_ - 1; i >= 0; --i) {
      while (pool_[x].level[i].next_idx != 0) {
        const int nxt = pool_[x].level[i].next_idx;
        if (less_than(pool_[nxt].score, pool_[nxt].member_id, score, member_id) ||
            (pool_[nxt].score == score && pool_[nxt].member_id == member_id)) {
          rank += pool_[x].level[i].span;
          x = nxt;
        } else {
          break;
        }
      }
      if (x != 0 && pool_[x].score == score && pool_[x].member_id == member_id) {
        return rank;
      }
    }
    return 0;
  }

  // O(log N) ZRANGE by Rank: Retrieve node at 1-based positional rank target_rank
  const Node* get_element_by_rank(std::size_t target_rank) const noexcept {
    std::size_t traversed = 0;
    int x = 0;
    for (int i = max_lvl_ - 1; i >= 0; --i) {
      while (pool_[x].level[i].next_idx != 0 &&
             traversed + pool_[x].level[i].span <= target_rank) {
        traversed += pool_[x].level[i].span;
        x = pool_[x].level[i].next_idx;
      }
      if (traversed == target_rank) return &pool_[x];
    }
    return nullptr;
  }
};