Detailed explanation of jump table of Redis data structure

The following column Redis Tutorial will give you a detailed explanation of the jump table of the Redis data structure. I hope it will be helpful to friends in need!

Preface

The jump list is an ordered data structure that maintains multiple pointers to other nodes in each node. To achieve the purpose of quickly accessing nodes. In this way, it may be difficult for us to understand, we can first recall the linked list.

1. Review jump table

1.1 What is a jump table

For a singly linked list, even if the data stored in the linked list is ordered, if we want To find certain data in it, you can only traverse the linked list from beginning to end. In this way, the search efficiency will be very low, and the time complexity will be very high, which is O(n).

If we want to improve the search efficiency, we can consider building an index on the linked list. Extract one node from every two nodes to the previous level, and we call the extracted level the index.

At this time, we assume that we want to find node 8. We can traverse in the index layer first. When we traverse to the node with a value of 7 in the index layer, we find that the next node is 9, then we need to The node 8 being searched for must be between these two nodes. We descended to the linked list level and continued traversing to find the node 8. Originally, we needed to traverse 8 nodes to find node 8 in a singly linked list, but now with the first-level index, we only need to traverse five nodes.

From this example, we can see that after adding a layer of index, the number of nodes that need to be traversed to find a node is reduced, which means that the search efficiency is improved. For the same reason, add another level. index.

We can see from the picture that the search efficiency has improved again. In our example, we have very little data. When there is a large amount of data, we can add multi-level indexes, and the search efficiency can be significantly improved.

A structure like this linked list plus multi-level index is a jump list!

2. Redis jump table

Redis uses jump table as one of the underlying implementations of ordered set keys. If an ordered set contains a large number of elements, or when the member of the element in the ordered set is a relatively long string , Redis will use a jump table as the underlying implementation of the ordered set key.

Here we need to think about a question - why does Redis use a jump table to implement it when there are a large number of elements or the members are relatively long strings?

From the above we can know that the jump list adds a multi-level index to the linked list to improve the efficiency of search, but it is a space-for-time solution, which will inevitably bring about a problem - the index is It takes up memory. The original linked list may store very large objects, but the index node only needs to store key values ​​and a few pointers, and does not need to store objects. Therefore, when the node itself is relatively large or the number of elements is relatively large, its advantage is It will inevitably be magnified, while the shortcomings can be ignored.

2.1 Implementation of skip table in Redis

The skip table of Redis is defined by two structures, Detailed explanation of jump table of Redis data structure and skiplist. The Detailed explanation of jump table of Redis data structure structure is used to represent the skip table node, and the zskiplist structure is used to save the jump. Information related to table nodes, such as the number of nodes, pointers to the head node and tail node, etc.

The above figure shows an example of a skip list. The leftmost one is the skiplist structure, which contains the following attributes.

• header: points to the header node of the jump table. The time complexity of locating the header node through this pointer program is O(1)

• tail: Points to the tail node of the jump table. The time complexity of locating the tail node of the table through this pointer program is O(1)

• level: Record the current jump table, The number of layers of the node with the largest number of layers (the number of layers of the header node is not included). Through this attribute, the number of layers of the node with the best layer height can be obtained in O(1) time complexity.

• length: Record the length of the jump table, that is, the number of nodes currently contained in the jump table (head nodes are not included). Through this attribute, the program can be O(1) Returns the length of the jump list in time complexity.

  On the right side of the structure are four Detailed explanation of jump table of Redis data structure structures, which contain the following attributes

• ## Level (level):
  Use 1, 2 in the nodes , L3 and other words mark each layer of the node, L1 represents the first layer, L represents the second layer, and so on.
  Each layer has two attributes: forward pointer and span. The forward pointer is used to access other nodes located at the end of the table, while the span records the distance between the node pointed by the forward pointer and the current node (the larger the span, the farther the distance). In the picture above, the arrow with a number on the connecting line represents the forward pointer, and that number is the span. When the program traverses from the beginning of the table to the end of the table, access will proceed along the forward pointer of the layer.
  Every time a new jump table node is created, the program randomly generates a value between 1 and 32 as the level based on the power law (powerlaw, the larger the number, the smaller the probability of occurrence) The size of the array, this size is the "height" of the layer.

• Backward pointer:
  The backward pointer of the node marked with BW in the node points to the previous node of the current node. The back pointer is used when the program traverses from the end of the table to the beginning. The difference with the forward pointer is that each node has only one backward pointer, so it can only move backward one node at a time.

• Score:
  1.0, 2.0 and 3.0 in each node are the scores saved by the node. In the jump table, nodes are arranged from small to large according to their saved scores.

• Member object (oj):
  o1, o2 and o3 in each node are the member objects saved by the node. In the same jump table, the member objects saved by each node must be unique, but the scores saved by multiple nodes can be the same: nodes with the same score will be sorted according to the size of the member objects in lexicographic order. , nodes with smaller member objects will be arranged in the front (direction closer to the head of the table), while nodes with larger member objects will be arranged in the back (direction closer to the end of the table).

2.2 Time complexity of common operations of Redis jump table

OperationTime complexityCreate a skip tableO(1) Release the given jump table and the nodes contained in itO(N)Add a new node with the given member and scoreAverage O (logN), worst case O(logN) (N is the length of the skip list)Delete the node containing the given member and score in the skip table The average is O(logN), the worst is O(logN) (N is the length of the jump table)Returns the ranking of the node with the given member and score in the tableAverage O(logN), worst O(logN) (N is the length of the jump table)Return the node in the given ranking Average O(logN), worst O(logN) (N is the length of the jump list)Given a score range, return the first score in the jump list that matches this range NodeO(1)Given a score range, return the last node in the jump table that matches this rangeAverage O( logN), worst O(logN) (N is the length of the jump table)Given a score range, except all nodes in the jump table that are within this rangeAverage O(logN), worst O(logN) (N is the length of the jump list)##Given a ranking range, except all the items in the jump list Nodes within this rangeGiven a score range (range), such as 0 to 15 , 20 to 28, and so on. If the score of at least one node in the jump table is within this range, then 1 is returned, otherwise 0 is returned.

Focus of this article

• The jump table is implemented based on a single linked list plus index
• The jump table improves the search speed by exchanging space for time
• Redis has The sequence set uses a skip list when the node elements are large or the number of elements is large.
• Redis's skip list implementation consists of two structures, zskiplist and zskiplistnode, where zskiplist is used to save skip table information (such as header nodes, Table tail node, length), and zskiplistnode is used to represent skip table nodes
• The layer height of each Redis skip table node is a random number between 1 and 32
• In the same In the jump table, multiple nodes can contain the same score, but the member object of each node must be unique. The nodes in the jump table are sorted according to the size of the score. When the scores are the same, the nodes are sorted according to the size of the member object. Sort.

Summary

Jump table may be a slightly unfamiliar data structure to us. This article briefly introduces the data structure of skip table and analyzes the use of skip table in Redis. The next article will continue to share the data structure integer collection used in Redis. stay tuned!

O(N), N is the number of nodes to be divided
O(N), N is the number of nodes to be removed.

The above is the detailed content of Detailed explanation of jump table of Redis data structure. For more information, please follow other related articles on the PHP Chinese website!