Redis jump table

brief introduction

By layering some nodes of an ordered set , Start with the top layer and search backwards , If the next The node is larger than the value to find or next The node is NULL, Start from this node , Lower one level and continue to look backward , By analogy , If found, the node is returned ; Otherwise return to NULL. Use this principle to find nodes , When the number of nodes is large , Some nodes can be skipped , Query efficiency is greatly improved , This is the basic idea of jump table .

Implementation process of jump table

Jump tables have the following properties ：

• The jump table consists of many layers
• The jump table has a header node , There is one in the header node 64 Layer structure , The structure of each layer contains a pointer to the next node of this layer , The number of nodes spanning the next node in this layer is span
• Except for the head node , The layer height of the node with the most layers is The height of the jump table （level）
• Each layer is an ordered list , Data increment
• except header Outside the node , An element appears in the upper ordered linked list , Then it must appear in the lower ordered linked list
• The last node of each layer of the jump table points to NULL, Indicates the end of the ordered linked list of this layer
• The jump table has a tail The pointer , Point to the last node of the jump table .
• The bottom level ordered linked list contains all nodes , The number of nodes at the bottom layer is The length of the jump table （length）（ Excluding header nodes ）
• Each node contains a backward pointer , The head node and the first node point to NULL; Other nodes point to the previous node at the bottom

Each node of the jump table maintains multiple pointers to other nodes , So look it up in the jump table 、 Insert 、 Some nodes can be skipped when deleting , Quickly find the nodes needed for the operation . in the final analysis , Jump table is to achieve the purpose of fast search by sacrificing space . The jump table is compared with the balance tree , The implementation is simpler , Just be familiar with the ordered linked list , You can easily master the jump table .

Structure of jump table and jump table nodes

Jump table node structure

Jump table node zskiplistNode The structure is as follows :

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

This structure contains the following attributes ：

• ele： Used to store string type data .
• score： Used to store sorting scores .
• backward： Back pointer , It can only point to the previous node at the bottom of the current node , The head node and the first node ----backward Point to NULL, Use... When traversing the jump table from back to front .
• level： Is a flexible array . The length of each node array is different , When generating jump table nodes , Randomly generate one 1~64 Value , The higher the value, the lower the probability of occurrence .
  level Each item of the array contains the following two elements ：
  • forward ： Point to the next node in this layer , Tail node forward Point to NULL.
  • span：forward The number of elements between the pointed node and this node .span The bigger the value is. , The more nodes skipped .

Jump table structure

In addition to the jump table node , You also need a jump table structure to manage nodes ,Redis Use zskiplist Structure , as follows ：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

This structure contains the following attributes ：

• header： Point to the jump table node . The head node is a special node of the jump table , its level The number of array elements is 64. The head node does not store any information in an ordered set member and score value ,ele The value is NULL,score The value is 0; It is not included in the total length of the jump table . When the header node is initialized ,64 An element of forward All point to NULL,span Values are 0.
• tail： Point to the jump footer node .
• length： Jump table length , Represents the total number of nodes except the head node .
• level： The height of the jump table .
  You can know from the properties of the jump table structure , The program can be O(1) Under the time complexity of , Get the head node of the jump table quickly 、 Tail node 、 Length and height .

Basic operation of jump table

Create a jump table

Redis5 The minimum height of middle node floor is 1, The maximum value is 64.
Redis Randomly generate a 1~64 Value , As the height of the new node , The higher the value, the lower the probability of occurrence .** After the node layer height is determined, it will not be modified .

Each node of the jump table is an element of an ordered set , When creating jump table nodes , The floor height of the node to be created 、 The score is 、member And so on . For each node of the jump table , We need to apply for memory to store .

zskiplistNode The last element of the structure is the flexible array , When applying for memory, you need to specify the size of the flexible array , The memory occupied by a node is zskiplistNode The memory size is the same as level individual zskiplistLevel The sum of the memory sizes of .
After allocating space , Initialize node variables .

The head node is a special node , Do not store ordered sets of member Information . The head node is the first inserted node in the jump table , Its level Each item of the array forward All for NULL,span Values are 0.

After creating the header node , You can create a jump table ：

• Create a jump table structure object zsl.
• take zsl The header node pointer of points to the newly created header node .
• The jump surface height is initialized to 1, The length is initialized to 0, The tail node points to NULL.

Insert node

Steps to insert a node ：

• Find the location to insert
• Adjust the height of the skip meter
• Insert node
• adjustment backward

Delete node

To delete a node ：

• Find the node that needs to be updated
• Set up span and forward

Delete jump table

After getting the jump table object , The... Of the ab initio node 0 Layer start , adopt forward The pointer traverses backwards step by step , Each time a node is encountered, it frees its memory . When the memory of all nodes is released , Release jump table object , That is, the deletion of the jump table is completed .

Learning links

redis A detailed explanation of