SoFunction
Updated on 2025-03-03

Redis Sorted Set implementation example of table jump

Preface

In Redis,Sorted Set (ordered set)It is a very important and efficient data structure. Unlike ordinary Sets, Sorted Set associates a score for each element and sorts it by this score. Sorted Set provides the ideal solution in many scenarios where quick insertion, deletion, find and range queries are required. And one of its underlying core data structures isSkip List,This structure effectively supports efficient operation of ordered sets.

This article will analyze the implementation principle of table skipping in depth and analyze the specific cases of Sorted Set in Redis to help you better understand the powerful performance sources of Redis Sorted Set.

What is a table jump?

Skip List is a type ofBalanced data structures, it accelerates the efficiency of search operations through multi-level indexing, first proposed by William Pugh in 1990. Its time complexity is similar to that of balanced binary trees, both of which are O(log n), but the implementation of table jumps is relatively simple and the operation is flexible.

The basic idea of ​​skipping tables is to improve data search efficiency by establishing multi-layer indexes based on linked lists. Each layer is a "thumbnail" of the next layer, so that when searching, you can quickly approach the target element by jumping.

Structure of jump table

The structure of the jump table is similar to a multi-layer linked list:

  • The first floorIt is a complete ordered list, and all data is on this level.
  • Second floor and aboveThis is an abstraction of some data, so that the amount of data in each layer is gradually reduced, but it remains in order.

Each element will decide whether to advance to the upper level with a certain probability. Therefore, the jump table has multiple pointers to different nodes, the lowest layer is similar to a normal linked list, while the upper layer pointer can span multiple nodes.

Time complexity of jump table

In the optimal case, the jump table reduces the number of layers and allows jump searches, and the time complexity of the average search, insertion and deletion is allO(log n), the space complexity isO(n). This feature makes table skip tables very suitable for implementing ordered sets, especially in scenarios like Redis that require efficient range query.

Sorted Set in Redis

Redis's Sorted Set is implemented through two core data structures:

  • Skip List: Used to sort elements by score, and supports sequential search, range search and other operations.
  • Hash table: Used to quickly locate elements based on the unique identifier (member) of the element to avoid repeated insertions.

Redis achieves the efficiency and flexibility of ordered sets through the combination of these two data structures.

The storage structure of Sorted Set

The storage structure of Redis Sorted Set iszset, it is internally composed of adictAnd onezskiplistComposition:

  • dict: Save the mapping relationship between members and corresponding scores, ensure member uniqueness, and the complexity of insertion and deletion operation time is O(1).
  • zskiplist: Used to skip tables sorted by scores, supports search by score range, delete range, etc., and the time complexity is O(log n).

This design ensures a balance between efficiency and stability of operations such as insertion, deletion and range query.

Implementation of skipping tables in Redis Sorted Set

1. Table jump node (zskiplistNode)

In Redis, each table hopping node not only contains the fraction and member information of the element, but also contains multiple pointers to other nodes, which are used to support the implementation of multi-layer indexing. RediszskiplistNodeThe definition of  is as follows:

typedef struct zskiplistNode {
    sds ele;  // Member (member)    double score;  // Score (score)    struct zskiplistNode *backward;  // Back pointer, used for reverse traversal    struct zskiplistLevel {
        struct zskiplistNode *forward;  // Forward pointer, point to the next node        unsigned int span;  // Span, used to quickly locate nodes    } level[];  // Multi-layer pointer for each node} zskiplistNode;
  • ele: Save member data.
  • score: Save the scores of the corresponding member.
  • backward: Used for reverse traversal and supports the function of two-way linked lists.
  • level: is an array with each element corresponding to a layer, saving a pointer to the next node.

2. Skip table structure (zskiplist)

RediszskiplistThe structure represents the entire jump table, which consists of the head node, the tail node, the maximum number of layers and the total number of nodes:

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;  // Jump the head and tail nodes of the table    unsigned long length;  // Number of nodes in the jump table    int level;  // The current maximum number of layers of the jump table} zskiplist;

3. Insert operation

When inserting a new element, the jump table searches the insertion position layer by layer from the high level to the low level, and inserts the new node into the linked list at the corresponding level. Every time a new node is inserted, it will randomly determine which layer it is promoted to. This randomness ensures the balance of table jumps.

The random layer generation algorithm used by Redis is as follows:

int zslRandomLevel(void) {
    int level = 1;
    while ((random() & 0xFFFF) < (0.25 * 0xFFFF)) {
        level += 1;
    }
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

zslRandomLevelThe function randomly generates the number of nodes based on the probability, so that the skip table can theoretically maintain the complexity at the log level.

Insert example:

Suppose we insert an element into the Sorted Set in Redis:

ZADD myzset 1 "apple"
  • Redis first assigns a number of layers to the element through a random algorithm.
  • Then, gradually find the appropriate insertion point from the highest level, update the pointers of the front and rear nodes in turn, and complete the insertion.

4. Search operations

The search operation of jump tables is achieved through layer by layer traversal from top to bottom. Each layer skips several nodes for quick searches until the target element is found at the lowest level. Due to the hierarchical design of the table jump, the time complexity of the search operation is O(log n).

Find examples:

For example, we want to query elements with a score of 3:

ZRANGE myzset 3 3

The jump table will start from the highest level, skip some nodes, and quickly find nodes with a score of 3.

5. Delete operation

When deleting an element, the jump table will first find the location of the target element and then remove the nodes from each layer. In order to maintain the balance of the data structure, the pointers at each level will be adjusted when deleting, and the number of layers that jump to the table will be reduced if necessary.

Delete Example:

Suppose we deletemyzsetElements with fraction 2:

ZREM myzset "banana"

The table jump will start from the beginning node and find it layer by layer.bananaThe location is located, and remove the element, and update the pointer relationship between the front and rear nodes.

Advantages and limitations of Redis table jump

Advantages

  • Efficient scope query: The jump table can quickly complete range search, ranking and other operations through hierarchical indexing.
  • Efficient insertion and deletion operations: The jump table maintains the complexity of insertion and deletion of O(log n), which is suitable for dynamic addition and deletion of large-scale data.
  • Simple implementation: Compared with balanced trees, the table jump structure is relatively simple and easier to implement and maintain.

Limited

  • Memory usage: To jump tables, you need to maintain multi-layer pointers for each node, which is relatively large in memory usage.
  • Performance fluctuations caused by randomness: Because the table jump uses a random algorithm to determine the number of node layers, performance fluctuations may occur, although this probability is extremely low.

Summarize

As the core data structure of Sorted Set, the skip table in Redis provides efficient sorting, inserting, deleting, and range search. Through the multi-layer indexing mechanism of table hopping, Redis can maintain the time complexity of O(log n) when processing ordered sets, while combining hash tables to ensure member uniqueness and fast access.

The design of the jump table is simple but powerful, and is one of the keys to Redis's high performance. After understanding its implementation principle, we can better use Redis's Sorted Set to optimize data query and operations in high concurrency environments.

If you are building a data system that requires sorting, range query or dynamic tuning, the combination of Redis's Sorted Set and table skipping is undoubtedly an efficient solution worth choosing.

This is the end of this article about the implementation example of Redis Sorted Set jump table. For more related contents of Redis Sorted Set jump table, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!