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

Preface

In Redis there is a data type that stores data using two different data structures simultaneously; this article explores why Redis does this and whether it doubles memory usage.

Five Basic Types – Set Object

Redis set objects are unordered collections of unique string elements.

The underlying data structures are intset and hashtable , distinguished by an encoding field.

intset Encoding

The intset (integer set) can store values of type int16_t , int32_t or int64_t while guaranteeing that no duplicate elements exist.

The intset data structure is defined in inset.h as follows:

typedef struct intset {
    uint32_t encoding;   // encoding method
    uint32_t length;    // number of elements in the set
    int8_t  contents[]; // actual elements
} intset;

A schematic diagram of an intset storage layout is shown below:

encoding

Inside an intset , the encoding field records the current integer storage type. There are three possible values:

INTSET_ENC_INT16 – each element in contents[] is a 16‑bit integer ( -32768 ~ 32767 ).

INTSET_ENC_INT32 – each element is a 32‑bit integer ( -2147483648 ~ 2147483647 ).

INTSET_ENC_INT64 – each element is a 64‑bit integer ( -9223372036854775808 ~ 9223372036854775807 ).

contents[]

Although the struct declares contents[] as int8_t , the actual stored type is determined by the encoding value.

Integer Set Upgrade

When a larger integer needs to be added, the set upgrades through four steps:

Expand the underlying array based on the new element’s size.

Convert existing elements to the new type and re‑insert them from back to front.

Place the new element at the head or tail (the upgrade condition guarantees it is either larger than all existing elements or smaller).

Update the encoding field and the length attribute.

Note: similar to string object encodings, once an integer set upgrades its encoding it never downgrades.

Upgrade Example

1. Suppose we have a set whose current encoding is int16_t and it stores three elements:

2. Inserting the integer 50000 (an int32_t ) cannot fit; a new space of 4 * 32 - 48 = 80 bytes is allocated.

3. The new array now holds four elements; the original third element is moved to positions 64‑95.

4. The second element is moved to positions 32‑63.

5. The first element is moved to positions 0‑31.

6. Finally the new integer 50000 is placed at positions 96‑127, and the encoding and length fields are updated.

hashtable Encoding

The hashtable structure for sets was described earlier in the hash‑object analysis; see the linked article for details.

intset and hashtable Encoding Conversion

Redis chooses intset encoding when both of the following conditions are satisfied:

All elements of the set are integers.

The number of elements is ≤ 512 (the threshold can be changed via the set-max-intset-entries configuration).

If either condition fails, Redis switches to hashtable encoding.

Set Object Common Commands

sadd key member1 member2 – add one or more members to the set.

sismember key member – test whether a member exists in the set.

srem key member1 member2 – remove members from the set (non‑existent members are ignored).

smove source dest member – move a member from one set to another.

smembers key – return all members of the set.

To verify the encoding behavior, the following commands are executed after flushall :

sadd num 1 2 3   // three integers → intset encoding
type num          // check type
object encoding num // view encoding

sadd name 1 2 3 test // three integers + a string → hashtable encoding
type name
object encoding name

The result shows that a set containing only integers uses intset , while a set with any non‑integer element uses hashtable .

Five Basic Types – Sorted Set Object

A sorted set differs from a regular set in that each element is associated with a double score, and the elements are ordered by score (from smallest to largest).

The underlying data structures are skiplist and ziplist , distinguished by an encoding field.

skiplist Encoding

A skiplist (also called a jump list) is used for sorted sets via the zset structure, which contains both a dictionary and a skiplist.

Jump List

Each node in a skiplist holds multiple forward pointers, allowing the algorithm to “skip” over large sections of the list. This yields an average search complexity of O(log N) , comparable to balanced trees but with a far simpler implementation.

In a plain linked list, finding an element requires O(N) scans; a skiplist reduces the number of steps dramatically, as illustrated:

Three possible traversal strategies for locating the element 35 are shown, with the highest level requiring only three pointer hops.

skiplist Storage Structure

Each node is a zskiplistNode (source server.h ):

typedef struct zskiplistNode {
    sds ele;                     // element (string)
    double score;                // score
    struct zskiplistNode *backward; // backward pointer
    struct zskiplistLevel {
        struct zskiplistNode *forward; // forward pointer for this level
        unsigned long span;            // number of nodes skipped by this forward pointer
    } level[];
} zskiplistNode;

The fields are:

level – an array of levels; a node may have multiple levels, each with its own forward pointer and span.

forward – pointer to the next node at the current level.

span – distance (in node count) to the next node at this level.

backward – pointer to the previous node (single backward link).

ele – the element stored as an sds string (must be unique).

score – the double‑precision score used for ordering; scores may repeat.

The skiplist itself is represented by:

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

The zset object wraps both a dictionary and a skiplist:

typedef struct zset {
    dict *dict;      // hash table for O(1) lookups
    zskiplist *zsl; // skiplist for ordered range queries
} zset;

Why Use Both Dictionary and Skiplist

The dictionary provides O(1) element lookup, while the skiplist enables ordered range queries with O(log N) complexity. Combining the two gives fast random access and efficient ordered operations, which is a key design advantage of Redis.

ziplist Encoding

Ziplist (compressed list) is also used in list and hash objects; see the linked article for a deeper dive.

ziplist and skiplist Encoding Conversion

A sorted set uses ziplist encoding when both conditions hold:

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

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

If either condition is violated, Redis switches to skiplist encoding.

Sorted Set Common Commands

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

zscore key member – return the score of a member.

zincrby key increment member – increment (or decrement) a member’s score.

zcount key min max – count members with scores in the given range.

zrange key start stop – return members by rank in ascending order.

zrevrange key start stop – return members by rank in descending order.

zrangebyscore key min max – return members whose scores fall within the range (default closed interval; can use '(' or '[' to control).

zrevrangebyscore key max min – same as above but in descending order.

zrank key member – get the zero‑based rank of a member (ascending).

zrevrank key member – get the zero‑based rank in descending order.

zlexcount key min max – count members by lexical range (requires '(' or '['; '-' and '+' denote negative/positive infinity).

To demonstrate encoding conversion, the configuration zset-max-ziplist-entries is set to 2 and Redis is restarted. Then the following commands are run:

zadd name 1 zs 2 lisi   // two elements → ziplist encoding
type name
object encoding name

zadd address 1 beijing 2 shanghai 3 guangzhou 4 shenzhen // four elements → skiplist encoding
type address
object encoding address

The output confirms that a sorted set with only two elements uses ziplist , while a set with more elements switches to skiplist .

Conclusion

This article analyzed the internal storage structures ( intset and skiplist ) of Redis set and sorted‑set objects, explained how sorted sets achieve ordering, and clarified why Redis stores data using both a dictionary and a skiplist to combine O(1) lookups with O(log N) range queries.