This is the 28th day of my participation in the August Challenge

A, definitions,

A skip list is an ordered data structure that enables fast access to nodes by maintaining multiple Pointers to other nodes in each node.

Here’s an extension:

For a single linked list, even if the data stored in the list is ordered, if we want to find some data in the list, we can only walk through the list from beginning to end. It’s going to be very inefficient, it’s going to be very time complex, order n.

If we want to improve the efficiency of its search, we can consider the way to build indexes on linked lists. Every two nodes are extracted to the next level, which we call the index.

As we can see, when we add a layer of index, the number of nodes that need to be traversed to find a node is reduced, that is to say, the search efficiency is improved, so we add another layer of index. When there is a large amount of data, we can add multi-level index, its search efficiency can be significantly improved.

Like this linked list plus multi-level index structure, is a skip list!

Second, data structure

1. Skip table data structure

typedef struct zskiplist { struct skiplistNode *header, *tail; // Unsigned long leng; Int level; } zskiplist;} zskiplist;Copy the code

2. Skip table node data structure

typedef struct zskiplistNode { struct zskiplist *backward; // double score; // obj *obj; Struct zskiplistNode {struct zskiplistNode *forward; // Forward pointer unsigned int span; } level[]; } zskiplistNode;Copy the code

Iii. Structure diagram

Redis skip lists are defined by zskiplistNode and skiplist structures, where zskiplistNode is used to represent skiplist nodes, and zskiplist Structure is used to hold information about skip table nodes, such as the number of nodes, Pointers to top and bottom nodes, and so on.

An example of a skip list with three members is as follows:

The figure above shows an example of a jump representation, with the skiplist structure at the far left containing the following properties.

  • Header: The time complexity of locating the head node through this pointer program is O(1).

  • Tail: Refers to the end node of a skip table. The time complexity of locating the end node is O(1).

  • Level: records the level of the node with the largest level in the current skip table (the level of the top node is not counted). Through this property, the node with the highest level can be obtained within O(1) time complexity.

  • Length: Records the length of the skip list. That is, the number of nodes the skip list currently contains (the head node is not counted). With this property, the program can return the length of the skip list in O(1) time complexity.

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

  • Layer (level) :

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

Each layer has two properties: a forward pointer and a 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 to which the forward pointer points 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. When the program traverses from the top of the table to the end of the table, access follows the forward pointer of the layer.

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 the “height” of the layer, according to the powerlaw (larger numbers are less likely to occur).

  • A pointer that goes backward:

The node is marked with the word BW as the back pointer to the node that preceded the current node. The back pointer is used when the program traverses from the end of the table to the beginning of the table. Unlike the forward pointer, there is only one backward pointer per node, so only one node can be backward at a time.

  • Score (score) :

The 1.0, 2.0, and 3.0 points in each node are the points held by the node. In a skip list, the nodes are arranged in ascending order of the points they hold.

  • Member object (OJ):

O1, O2, and O3 in each node are the member objects stored in the node. Jump at the same table, each node holds a member of the object must be unique, but multiple nodes to save score can be the same: to score the same node according to the members of the object in dictionary order size to sort, member objects smaller node will be at the top (near the direction of the header), while the member objects larger node will row behind (near the footer Direction).

Four, Redis linked list characteristics

  • Support average O(logN), worst O(N)

  • In the same skip table, multiple nodes can contain the same score, but the member object of each node must be unique.

  • The nodes sort by the size of the points, and when the points are the same the nodes sort by the size of the member objects.

5. Applicable scenarios

1. Ordered sets

2. Internal data structure of cluster nodes

– END –

Author: The road to architecture Improvement, ten years of research and development road, Dachang architect, CSDN blog expert, focus on architecture technology precipitation learning and sharing, career and cognitive upgrade, adhere to share practical articles, looking forward to growing with you. Attention and private message I reply “01”, send you a programmer growth advanced gift package, welcome to hook up.

Thanks for reading!