Why Redis Uses Dual Data Structures for Sets and Sorted Sets

Set Object Encoding

intset encoding

Redis stores a set of pure integer elements in an intset structure. The structure holds the current integer size (encoding), the number of elements (length) and a flexible array contents[] whose actual element type is determined by the encoding.

typedef struct intset {
    uint32_t encoding;   // encoding type (INT16, INT32, INT64)
    uint32_t length;     // number of elements
    int8_t contents[];    // element values (actual type depends on encoding)
} intset;

INTSET_ENC_INT16 : values from -32768 to 32767.

INTSET_ENC_INT32 : values from -2147483648 to 2147483647.

INTSET_ENC_INT64 : values from -9223372036854775808 to 9223372036854775807.

Upgrade process

When a new element cannot be represented by the current encoding, Redis performs four steps:

Allocate a new underlying array sized for the larger integer type.

Convert all existing elements to the larger type and copy them back-to-front.

Insert the new element at the appropriate end (the new element is either smaller than all existing values or larger than all of them).

Update the encoding field and the length field.

intset encoding never downgrades, similar to string object encodings.

Conversion to Hashtable

Redis switches a set from intset to a hash table when either a non‑integer element is added or the number of elements exceeds the configurable limit set-max-intset-entries (default 512).

Set commands

sadd key member1 [member2 ...]

– add one or more members. sismember key member – test whether a member exists. srem key member1 [member2 ...] – remove members. smove source dest member – move a member from one set to another. smembers key – return all members of the set.

Sorted‑Set Object Encoding

skiplist encoding

Sorted sets associate each member with a double‑precision score. For sets larger than a size threshold or when the total element length exceeds a limit, Redis stores the data in a skiplist ( zskiplist) together with a dictionary ( zset) to achieve O(log N) range queries and O(1) look‑ups.

typedef struct zskiplistNode {
    sds ele;                     // element string
    double score;                // score value
    struct zskiplistNode *backward; // backward pointer
    struct zskiplistLevel {
        struct zskiplistNode *forward; // forward pointer
        unsigned long span;            // distance to next node
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // head and tail pointers
    unsigned long length;               // number of nodes
    int level;                          // max level
} zskiplist;

typedef struct zset {
    dict *dict;      // hash table for O(1) look‑ups
    zskiplist *zsl; // skiplist for ordered access
} zset;

ziplist encoding

For small sorted sets Redis uses a compact ziplist representation. The ziplist is selected when both of the following conditions hold:

The number of elements is less than zset-max-ziplist-entries (default 128).

The total serialized length of all elements is less than zset-max-ziplist-value (default 64 bytes).

Sorted‑Set commands

zadd key score1 member1 [score2 member2 ...]

– add members with scores. zscore key member – get a member’s score. zincrby key increment member – increment a member’s score (increment may be negative). zrange key start stop – return members in ascending score order. zrevrange key start stop – return members in descending score order. zrank key member – get the 0‑based rank of a member in ascending order. zrevrank key member – get the 0‑based rank in descending order. zcount key min max – count members with scores in the given interval. zlexcount key min max – count members in a lexical range (supports open/closed intervals).

In summary, Redis implements set objects with two interchangeable encodings: a memory‑efficient intset for pure integer sets and a hash table for mixed or large sets. Sorted‑set objects combine a dictionary (for O(1) member look‑ups) with a skiplist (for O(log N) ordered range queries). When a sorted set is small enough, Redis falls back to a ziplist to save memory. The described structures and commands allow developers to understand the internal representation and to choose appropriate operations for their workloads.