Shulou(Shulou.com)06/01 Report--

Xiaobian to share with you what is the jump table of Redis data structure, I believe most people still do not know how, so share this article for everyone's reference, I hope you have a lot of harvest after reading this article, let's go to understand it together!

preface

A jump table is an ordered data structure that allows fast access to nodes by maintaining multiple pointers to other nodes in each node. This may be difficult for us to understand, but we can first recall the linked list.

I. Review the jump table 1.1 What is the jump table

For a single-linked list, even if the data stored in the list is ordered, if we want to find a certain data in it, we can only traverse the list from beginning to end. The search time complexity is O(n).

If we want to improve the efficiency of its search, we can consider the way to build an index on the list. Every two nodes extract a node to the next level, we call the extracted level index.

At this time, we assume that to find node 8, we can first traverse the index layer, when traversing to the index layer with a value of 7, we find that the next node is 9, then the node 8 to be found must be between these two nodes. We descend to the linked list level and continue to traverse to find the node 8. Originally we found 8 nodes in the single-linked table to traverse 8 nodes, but now we only need to traverse 5 nodes after having a first-level index.

From this example, we can see that after adding a level of index, the number of nodes that need to be searched for a node is reduced, that is, the search efficiency is improved. Similarly, another level of index is added.

From the graph we can see that the search efficiency has improved. In the example we have very little data, when there is a lot of data, we can increase the multi-level index, its search efficiency can be significantly improved.

Like this linked list plus multi-level index structure, is the jump table!

II. Redis jump table

Redis uses jump tables as one of the underlying implementations of ordered set keys. If an ordered set contains a large number of elements, or if the members of an ordered set are long strings, Redis uses jump tables as the underlying implementation of ordered set keys.

Here we need to think about a question-why does Redis use jump tables when it has a large number of elements or long strings?

From the above we can know that the jump table adds multi-level indexes to the linked list to improve the efficiency of the search, but it is a space-for-time scheme, which will inevitably bring a problem-the index is memory-occupied. The original linked list may store very large objects, and index nodes only need to store key values and a few pointers, and do not need to store objects, so when the node itself is relatively large or the number of elements is relatively large, its advantages will inevitably be magnified, and the disadvantages can be ignored.

2.1 Implementation of Jump Table in Redis

The jump table of Redis is defined by two structures, zskiplistNode and skiplist. The zskiplistNode structure is used to represent the jump table nodes, while the zskiplist structure is used to store the relevant information of the jump table nodes, such as the number of nodes, and pointers to the head nodes and tail nodes.

The figure above shows an example of a skip representation, where the leftmost is a skiplist structure that contains the following attributes.

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

O (1): The time complexity of the algorithm is O(1).

level: Record the number of layers of the node with the largest number of layers in the current jump table (excluding the number of layers of the header node). Through this attribute, you can obtain the number of layers of the node with the best layer in O(1) time complexity.

length: Record the length of the jump table, i.e., the number of nodes currently contained in the jump table (excluding header nodes). With this attribute, the program can return the length of the jump table in O(1) time complexity.

To the right of the structure are four zskiplistNode structures that contain the following attributes

Level:

Each layer of the node is marked with the words 1, 2, L3, etc.,L1 represents the first layer,L represents the second layer, and so on.

Each layer carries 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 to by the forward pointer and the current node (the larger the span, the farther the distance). In the figure above, the arrow with a number on the line represents the forward pointer, and that number is the span. As the program traverses from the head to the tail of the table, access follows the forward pointer of the layer.

Each time a new jump table node is created, the program randomly generates a value between 1 and 32 as the size of the level array according to the power law (the larger the number, the less likely it is to occur), which is the "height" of the layer.

Backward pointer:

The backward pointer of a node marked with BW points to the node immediately preceding the current node. The back pointer is used when the program traverses from the end of the table to the head. Unlike the forward pointer, there is only one backward pointer per node, so only one node can be backward at a time.

Score:

1.0, 2.0, and 3.0 in each node are the scores held by the node. In the jump table, the nodes are arranged in descending order according to the scores they hold.

Member object (oj):

o1, o2, and o3 in each node are the member objects held by the node. In the same jump table, each node must have a unique member object, but multiple nodes can have the same score: nodes with the same score will be sorted according to the size of the member object in the dictionary order, nodes with smaller member objects will be ranked first (toward the head), and nodes with larger member objects will be ranked later (toward the tail).

2.2 O (logN): O (logN): O (logN: O (logN): O (logN: O(logN), O (logN). O(logN), O (logN). O(logN), O (logN) O (logN) is the length of the jump table. O (logN) is the length of the jump table. Given a range of scores, O(logN) is the worst case, except for all the nodes in the jump table that fall within this range.(N is the length of the jump table) Given a ranking range, divide all nodes in the jump table within this range,N is the number of divided nodes Given a range of scores, such as 0 to 15, 20 to 28, and so on, if at least one node in the jump table has a score within this range, then return 1, otherwise return 0O(N), N is the number of nodes to be divided. This paper focuses on the skip table. The skip table is implemented based on the single-linked table and index. The skip table improves the search speed in the way of space for time. Redis ordered set uses the skip table to implement Redis when the node element is large or the number of elements is large. The skip table implementation consists of two structures, zskiplist and zskiplistnode, where zskiplist is used to store the skip table information.(For example, the head node, the tail node, the length), and zskiplistnode is used to represent the jump table node Redis The height of each jump table node is a random number between 1 and 32. In the same 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 score size. The above is Redis data structure jump table is what all the content, thank you for reading! I believe that everyone has a certain understanding, hope to share the content to help everyone, if you still want to learn more knowledge, welcome to pay attention to the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.