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

This article will explain in detail the example analysis of the jump table in the redis data structure. The editor thinks it is very practical, so I share it with you for reference. I hope you can get something after reading this article.

Jump table definition:

Jump table (skiplist) is an ordered data structure, which can quickly access nodes by maintaining multiple pointers to other nodes in each node.

The jump table supports node lookup with average O (logN) and worst O (N) complexity, and can also batch process nodes through sequential operations.

Jump table usage scenarios:

Redis uses the jump table as one of the underlying implementations of the ordered set key. If an ordered set contains a large number of elements, or if the member of the elements in the ordered set is a long string, Redis will use the jump table as the underlying implementation of the ordered set key. Unlike linked lists, dictionaries and other data structures are widely used in Redis, Redis only uses jump tables in two places. One is to implement ordered collection keys, the other is to be used as an internal data structure in cluster nodes, and beyond that, jump tables have no other use in Redis.

The jump table consists of:

Redis's jump table is defined by two structures, redis.h/zskiplistNode and redis.h/zskiplist.

The zskiplistNode structure is used to represent the jump table node:

Layer (level): each layer of the node is marked with the words L1, L2, L3, etc., L1 for the first layer, L2 for the second layer, and so on. Each layer has two properties: forward pointer and span. The forward pointer is used to access other nodes at the end of the table, while the span records the distance between the node the forward pointer points to and the current node. In the picture 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 header to the footer, the access occurs along the forward pointer of the layer. Backward pointer: a backward pointer in a node that marks a node with the word BW, pointing to the previous node at the current node. The back pointer is used when the program traverses from the footer to the header. Scores (score): 1.0,2.0 and 3.0 in each node are the scores saved by the node. In the jump table, the nodes are arranged from small to large according to their saved scores. Member objects (obj): o1, o2, and o3 in each node are the member objects saved by the node.

Zskiplist structure: used to hold information about jump table nodes, such as the number of nodes, pointers to header and footer nodes, and so on.

Header: points to the header node of the jump table. Tail: the footer node pointing to the jump table level: record the number of layers of the node with the largest number of layers in the current jump table (the number of layers of the header node is not counted) length: record the length of the jump table, that is, the jump table currently contains the number of nodes (header nodes are not counted

Jump table display: zskiplistNod structure details:

Structure definition:

The level array of jump table nodes can contain multiple elements, each containing a pointer to other nodes. Programs can use these layers to speed up access to other nodes. In general, the more layers, the faster access to other nodes.

Query traversal process:

1) the iterator first accesses the first node (header) of the jump table, and then moves from the forward pointer of the fourth layer to the second node in the table. 2) at the second node, the program moves along the forward pointer of the second layer to the third node in the table. 3) in the third node, the program also moves along the forward pointer of the second layer to the fourth node in the table. 4) when the program moves along the forward pointer of the fourth node again, it encounters a NULL, and the program knows that it has reached the end of the jump table, so it ends the traversal.

Take an example of a query:

If you want to query a location with a value of 3.0, traverse from the head node to 3.0, and go through the layer along the way: the search process goes through only one layer, and the span of the layer is 3, so the position of the target node in the jump table is 3. Isn't it soon!

Details of the structure of zskiplist:

Structure definition:

By using a zskiplist structure to hold these nodes, the program can more easily process the entire jump table, such as quickly accessing the header and footer nodes of the jump table, or quickly obtaining information such as the number of jump table nodes (that is, the length of the jump table).

Jump table common api on "sample analysis of jump tables in redis data structures" this article shares here, I hope the above content can be of some help to you, so that you can learn more knowledge, if you think the article is good, please share it out for more people to see.

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.