What is a jump list

Skiplist is an ordered data structure. It is designed to achieve fast access to nodes by maintaining multiple Pointers to other nodes in each node.

Skip lists can find nodes in either the average O(logN) or the worst O(N) time complexity, and can batch nodes through sequential operations.

Application scenarios of jump list

Bidirectional linked list, SDS, dictionary and other data structures are widely used in different places of Redis, while there are only two places where jump list is used in Redis, one is the Zset data type of Redis, and the other is used as the internal data structure of nodes in Redis cluster.

Skip list node structure content

Before we look at the skip list structure content, let’s look at the skip list node structure content:

Specific structure code:

Typedef struct zskiplistNode {// robj *obj; // double score; Struct zskiplistNode *backward; Struct zskiplistNode *forward; struct zskiplistNode *forward; // span unsigned int span; } level[]; } zskiplistNode;Copy the code

The red boxes in the figure are the three jump list nodes

layer

The level attribute of a skip list node is an array in which each element contains a forward pointer to another node. The maximum length of the array is 32. Programs can use forward Pointers in these layers to speed up access to other nodes.

In general, the more layers you have, the faster you can access other nodes.

Each time a new skip list node is created, the program randomly generates a value between 1 and 32 as the size of the level array, which is also the height of the layer, according to the power law (larger numbers are less likely to occur).

Forward Pointers

The forward pointer inside each level is used to access nodes from the table head to the table tail. Generally, the forward pointer points to a layer of the next skip list node, otherwise it is NULL.

span

The span property in each level is the span, which records the distance between two jump list nodes. When the forward pointer points to a NULL value, the span is 0.

Span the function of this attribute is: when looking for a node, the span of all layers visited along the way is summed up, and the result is the rank of the target node in the skip list, that is, the rank.

The back pointer

A backward attribute in a skip list node is a backward pointer used to access a skip list node from the end of the table to the head.

The backward pointer only points to NULL for the first jump list node. The other nodes basically point to the memory address of the previous node.

Unlike the forward pointer in the layer, which has only one backward pointer per node and can only go to the previous node at a time, the forward pointer can have multiple backward Pointers per node and can go to span nodes at a time.

score

The score attribute in the skip list node is the score value, which is a floating point number of type double. All nodes in the skip list are sorted according to the score value from lowest to highest.

Members of the object

The obj attribute in the skip list node is the member object, which is a pointer to a string object that holds the value of an SDS structure.

In the same skip list, each node must hold unique member objects, but the scores of multiple nodes can be the same. When nodes have the same score, they are sorted by the size of the member objects in the lexicographical order, with the smaller ones before the nodes in the skip list and the larger ones after.

Skip list structure content

In the above multiple jump list node structure, you can form a jump list.

Skip list structure specific code:

Typedef struct zskiplist {// struct zskiplistNode *header, *tail; // The number of nodes in the table unsigned long length; Int level; int level; } zskiplist;Copy the code

An overview of the structure of a specific skip list:

The attributes header and tail are Pointers pointing to the head node and the tail node of the jump list respectively. Through these two attributes, the time complexity of the node searching the head and tail of the table is O(1).

The length property represents the number of nodes in the jump list. The time complexity of finding the length of the jump list is also O(1).

The level attribute stores the number of layers of the node with the highest middle height of the jump list node, which does not include the table header node. The time complexity of obtaining the number of layers of the node with the highest middle height is still O(1).

Related implementation of jump list

Creating a jump list

When creating a jump list, zmalloc is called to allocate memory for the jump list, zslCreate is called, the number of layers is initialized to 1, the length is 0, and the tail pointer is NULL. ZslCreateNode is called to create a jump list node. The back pointer of the head node is set to NULL, the forward pointer of each layer is set to NULL, and the span is set to 0

The zslCreateNode function is created by first allocating memory space for the head node, then setting the associated attribute values to 0, member objects to NULL, and generating 32 layers.

zskiplistNode *zslCreateNode(int level, double score, Robj *obj) {zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel)); // set attribute zn->score = score; zn->obj = obj; return zn; } zskiplist *zslCreate(void) { int j; zskiplist *zsl; ZSL = zmalloc(sizeof(* ZSL)); ZSL ->level = 1; zsl->length = 0; T = O(1) ZSL ->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL); for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) { zsl->header->level[j].forward = NULL; zsl->header->level[j].span = 0; } zsl->header->backward = NULL; ZSL ->tail = NULL; return zsl; }Copy the code

Create a jump list diagram:

Insert the skip list node

Inserting a skip list node can be divided into approximately four steps:

  1. Find the insertion location of the new node in each layer
  2. Gets a random value as the number of layers for the new node
  3. Create a new node and insert the jump list
  4. Additional Information Updates
zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) { zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; unsigned int rank[ZSKIPLIST_MAXLEVEL]; int i, level; redisAssert(! isnan(score)); X = ZSL ->header; for (i = zsl->level-1; i >= 0; i--) { rank[i] = i == (zsl->level-1) ? 0 : rank[i+1]; while (x->level[i].forward && (x->level[i].forward->score < score || (x->level[i].forward->score == score && compareStringObjects(x->level[i].forward->obj,obj) < 0){ rank[i] += x->level[i].span; x = x->level[i].forward; } update[i] = x; } // 2. Get a random value for the new node level = zslRandomLevel(); if (level > zsl->level) { for (i = zsl->level; i < level; i++) { rank[i] = 0; update[i] = zsl->header; update[i]->level[i].span = zsl->length; } zsl->level = level; X = zslCreateNode(level,score,obj); for (i = 0; i < level; i++) { x->level[i].forward = update[i]->level[i].forward; update[i]->level[i].forward = x; x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]); update[i]->level[i].span = (rank[0] - rank[i]) + 1; } for (i = level; i < zsl->level; i++) { update[i]->level[i].span++; } // 4. Update additional information // Set new node's backward pointer x->backward = (update[0] == ZSL ->header)? NULL : update[0]; if (x->level[0].forward) x->level[0].forward->backward = x; else zsl->tail = x; ZSL ->length++; return x; }Copy the code

Specific explanation:

1. Find the insertion position of the new node in each layer

Since jump list maximum layer level traversal, corresponding level layer header from a pointer to the first node to traverse, if the node’s score is greater than new node score or the same score, but the members of the node object is larger than the new value of the dictionary, then the node of the previous record to update an array, And record the span into the rank array.

2. Get a random value as the number of layers of the new node

Generates a random value for the number of layers of the new node. If the value of the level is greater than that of the other nodes, each level greater than the original level is iterated, the span of each level is initialized to the current length value, and recorded in the UPDATE array. It also initializes the span of the corresponding index in the rank array.

Finally, update the new level to the level property of the jump list.

3. Create a new node and insert the jump list

Call the zslCreateNode function to create a new node and set the initial values of the associated attributes.

Through the new level value, the forward pointer of each layer of the new node is changed to point to the node with the index of the previous UPDATE array. Then, the forward pointer of the node with the index of the previous UPDATE array is changed to point to the new node, and the new span value of each node is recorded.

4. Additional information updates

Adjust the back pointer for the new node and increase the length of the jump list by 1

Skip list lookup

Single linked list structure search, even if the storage data in the list is ordered, but its search time complexity is still O(n), from the head of the table to the end of the table.

Such a result is obviously very bad. In order to solve the problem of search efficiency, the skip list establishes a forward pointer on the layer of each node, which can be understood as an index. It can directly find the values of the third and fourth nodes from the first node, which can improve the efficiency of O(n) a lot.

This is a space for time design. Index creation means more memory, but time lookup efficiency is improved.

Specific search process:

The route to find a node with a score of 17 in the jump list is shown by the red arrow.

First jump list is from one of the biggest layer into small traversal, access to the second floor of the first node first, score is 1, smaller than 17, so continued to advance to the second floor the first node pointer position traverse, now find the score of 9 nodes, then or younger than 17 because it is over, continue to traverse, access to the score for 21 nodes, because 21 than 17, At this point, we go to the first layer with a score of 9, traverse forward in the direction of the pointer, and finally obtain the node with a score of 17.

The higher the number of layers in the skip list, the faster the search efficiency may be.

As shown in the figure, when looking for the node with a score of 17, the node with a score of 17 can be obtained directly from the third layer forward pointer of the first node.

According to the above description, the search of skip list is similar to the binary search method, which directly obtains the value of the non-next node through the forward pointer of each layer, and then accelerates the search efficiency by the ratio size. This search efficiency can be reduced to an average order logN time.

conclusion

Through the concept of Redis jump list, concrete structure content, detailed implementation of specific related operations to learn, to understand the specific existence of jump list, in Redis is mainly the implementation of Zset data structure.

Reference: Redis Design and Implementation

For more Java backend development related technologies, you can follow the public account “Red Orange ah”.