Data Structure and Algorithm analysis Redis ordered Set zSET implementation principle (skip table)

A skip list is an ordered data structure that maintains multiple Pointers to other nodes on each node for fast access. Skip lists have an average complexity of O (logN) and a worst complexity of O (N) for insert, delete, and lookup operations, which is comparable to red-black trees, but much simpler to implement. Zset in Redis is the implementation of ordered collections using skip lists. It has the following properties:

1. Consisting of many layers;
2. Each layer is an ordered linked list, arranged from top to bottom, and contains at least two linked list nodes, head node in front and nil node in the back.
3. The lowest linked list contains all the elements;
4. If an element appears in a list at a certain level, then all lists below that level also appear (the elements at the upper level are subsets of the elements at the current level).
5. Each node in a linked list contains two Pointers, one to the next linked list node at the same level and the other to the same linked list node at the next level.
   
   
   
   As shown in the figure above, there is a linked list of ordered numbers. If we want to find the numbers <16,23,25,31>, the simple way is to go through them in O(N) time. Small amounts of data are fine, but large amounts of data can be time-consuming. This is where we need to optimize, to find a linear order list, we usually use dichotomy search, order LogN time. But linked lists do not apply dichotomy to find them (linked lists do not have the continuous subscripts that linear lists do to determine the middle position). The result is a hop table, which is a randomized data structure, similar to a binary search tree, where we extract nodes as indexes. > The simple way to iterate over these numbers is O(N). Small amounts of data are fine, but large amounts of data can be time-consuming. This is where we need to optimize, to find a linear order list, we usually use dichotomy search, order LogN time. But linked lists do not apply dichotomy to find them (linked lists do not have the continuous subscripts that linear lists do to determine the middle position). The result is a hop table, which is a randomized data structure, similar to a binary search tree, where we extract nodes as indexes. As follows:
   
   
   
   We extracted <13,19,25,34> as a first-level index to reduce the number of comparisons. Similarly, a primary index can create a secondary index, as follows, in the case of massive data this method will undoubtedly greatly reduce the query time O(logN)
   
   
   
   Skip list structure in Redis
   
   In the above simple understanding of the basic meaning of skip list and the idea of implementation. In Redis, a skip table is defined in server.h and consists of two constructs representing the zskiplistNode and zskilist of the skip table node. The zskiplistNode structure is used to represent skiplist nodes, and the zskiplist structure is used to store information about skiplist nodes. The source code is as follows:

typedef struct zskiplistNode {
    // The object of the node's corresponding member, usually SDS
    robj *obj;
    // the order of the skip list is sorted according to the score value
    double score;
    // Store Pointers to successor nodes
    struct zskiplistNode *backward;
    / / hierarchy
    struct zskiplistLevel {
        // Store the pointer to the precursor node
        struct zskiplistNode *forward;
        / / span
        unsigned int span;
    } level[];
} zskiplistNode;


typedef struct zskiplist {
    // The head and tail nodes of the skip table
    struct zskiplistNode *header, *tail;
    // The number of nodes in the skip list
    unsigned long length;
    // The maximum number of nodes in the middle layer of the table
    int level;
} zskiplist;
Copy the code

Level [] is a very important attribute in the skip list. When initializing a skip list node, a random level size is generated for it. This size is usually between 1 and 32 (it doesn’t need to be very large, assuming that 2^32 is a large 4.2 billion + in extreme average cases), as the size of the level array. Each element in the array contains a forward pointer to the other nodes to speed up access to them. As shown in the figure below, this level is generated randomly, so the level that each node has is not necessarily the same, but at least 1 level. Suppose the linked list <13,16,19,34>



Its skip list structure might look like this (note that it is possible, since the Level of each node is random):