Getting started with redis - Chapter 4 - data structures and objects - jump table

Skip list （skiplist） Is an ordered data structure , It maintains multiple pointers to other nodes in each node , So as to achieve the purpose of fast access to nodes .Redis Using the jump table as one of the underlying implementations of the ordered set key , If an ordered set contains more elements , Or members of elements in an ordered collection （member） When it's a long string ,Reids Will use the jump table as the underlying implementation of the ordered set key .

And the list 、 Data structures such as dictionaries are widely used in Redis It's different inside ,Redis There are only two places where the jump table is used , One is to implement an ordered set key , The other is used as internal data structure in cluster nodes .

The realization of jump table ：

Redis The jump table is made up of redis.h/zskiplistNode and redis.h/zskiplist Two structural definitions ：

typedef struct zskiplistNode {
  struct zskiplistLevel {
    struct zskiplistNode *forward; //  Forward pointer  
    unsigned int span;             //  span 
  }level[];  
  struct zskiplistNode *backward;  //  Back pointer 
  double score;                    //  The score is 
  robj *obj;                       //  member object 
}zskiplistNode;

typedef struct zskiplist {
  struct zskiplistNode *header, *tail; //  Pointer to header node and footer node 
  unsigned long length;                //  Number of nodes in the table （ Header nodes are not counted ）
  int level;                           //  The maximum number of layers in the table （ Header nodes are not counted ）
}

1. layer ： Jump table node level Arrays can contain multiple elements , Each element contains a pointer to other nodes , Programs can use these layers to speed up access to other nodes , Generally speaking , The more layers there are , The faster you can access other nodes . Every time a new jump table node is created , The program is based on the power law （ The larger the number, the smaller the probability of occurrence ） Randomly generate an interval between 1 ~ 32 The value between is taken as level Size of array , This is the height of the floor .
2. Forward pointer ： Each layer has a forward pointer to the end of the table (level[i].forward attribute ), Used to access nodes from header to footer .
3. span ：(level[i].span) Used to record the distance between two nodes , Span is used to calculate the rank of nodes , In the process of finding a node , Add up the spans of all layers visited along the way , The result is the position of the target node in the jump table .
4. Back pointer ： Used to access nodes from the end of the table to the head .
5. Scores and members ： The nodes in the jump table are arranged from small to large according to the score , The member object is a pointer , Point to a string object , The string object holds a SDS value .

In the same jump table , The member objects saved by each node must be unique , But the scores saved by the node can be the same , Nodes with the same score will be sorted by the size of the member objects in the dictionary order .