Redis Set and Sorted Set Internal Encodings: intset, Hashtable, Skiplist and Ziplist

Redis uses two different internal data structures to store collection objects, and this article explains the reasons behind that design, focusing on the set and sorted‑set types.

Set Object

A Redis set is an unordered collection of unique strings. Its underlying representation can be either intset or a hash table, distinguished by an internal encoding field.

intset Encoding

The intset stores integer values using one of three integer types: int16_t , int32_t or int64_t . The structure is defined as:

typedef struct intset {
    uint32_t encoding;   // encoding type
    uint32_t length;     // number of elements
    int8_t  contents[];  // actual elements
} intset;

Depending on the current encoding , the contents[] array holds values of the corresponding integer size, with ranges:

INTSET_ENC_INT16 : values from -32768 to 32767

INTSET_ENC_INT32 : values from -2147483648 to 2147483647

INTSET_ENC_INT64 : values from -9223372036854775808 to 9223372036854775807

When a new element does not fit the current integer size, the intset is upgraded. The upgrade consists of four steps: expanding the array, converting existing elements to the larger type, inserting the new element at the head or tail, and updating the encoding and length fields. The article provides a detailed illustrated example of upgrading from int16_t to int32_t .

Hashtable Encoding

If the set contains any non‑integer element or the number of elements exceeds the configurable limit set‑max‑intset‑entries (default 512), Redis switches to a hash table representation. The hash table provides O(1) look‑ups for membership tests.

Sorted‑Set Object

A sorted set associates each member with a double‑precision score and maintains the members ordered by score. Its internal representation can be either a skiplist (for large or complex sets) or a ziplist (for small, compact sets).

skiplist Encoding

The skiplist node is defined as:

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

A skiplist consists of multiple levels (1‑32) generated according to a power‑law distribution. Each level provides forward pointers that allow O(log N) search, while the hash table part of a zset gives O(1) member‑to‑score look‑ups. The combined structure is:

typedef struct zset {
    dict *dict;          // dictionary for member → score
    zskiplist *zsl;      // skiplist for ordered traversal
} zset;

Using both a dictionary and a skiplist lets Redis achieve fast exact look‑ups (O(1)) and efficient range queries (O(log N)) without extra sorting overhead.

ziplist Encoding

When a sorted set contains fewer than zset‑max‑ziplist‑entries (default 128) members and the total serialized length of all members is less than zset‑max‑ziplist‑value (default 64 bytes), Redis stores the set as a compact ziplist . This saves memory for tiny sorted sets.

Common Commands

For sets:

sadd key member1 member2 – add members

sismember key member – test membership

srem key member1 member2 – remove members

smove src dst member – move a member

smembers key – list all members

For sorted sets:

zadd key score1 member1 [score2 member2 ...] – add members with scores

zscore key member – get a member's score

zincrby key increment member – increment a score

zrange key start stop – get members in score order

zrevrange key start stop – get members in reverse score order

zrangebyscore key min max – range query by score

zrank key member – get rank (ascending)

zrevrank key member – get rank (descending)

The article demonstrates these commands with example sessions, showing how the type and object encoding commands reveal the underlying representation before and after inserting integer‑only versus mixed‑type elements.

Conclusion

The article analyses the internal storage mechanisms of Redis set and sorted‑set objects, explains the intset ↔ hashtable and skiplist ↔ ziplist encoding switches, and clarifies why Redis combines two data structures for sorted sets to achieve both O(1) look‑ups and O(log N) ordered operations.