A skip list is an ordered data structure that maintains multiple Pointers to other nodes in each node to achieve fast access to nodes. Skip lists support node lookup with average O(logN) and worst O(N) complexity, and batch processing of nodes through sequential operations.

5.1 Implementation of skip lists

Redis skip lists are defined by the zskiplistNode and zskiplist structures.

The zskiplistNode is used to represent skip nodes, and the Zskiplist structure is used to hold information about skip table nodes, such as the number of nodes, Pointers to the top and bottom of the table, and so on.

Figure 5-1 shows an example of a skiplist. The zskiplist structure at the far left of the image contains the following properties:

  • Header: Points to the head node of the skip list
  • Tail: Points to the tail node of the skip list
  • Level: records the level of the node with the largest level in the current skip table
  • Length: records the length of the skip list

Located to the right of the ZSkiplist structure are the four zskiplistNode structures that contain the following properties:

  • Layer: Each layer of the node is marked with words L1, L2, L3, etc. L1 represents the first layer, and so on. Each layer has two properties: the forward pointer and the 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 and the span point and the current node. As shown in Figure 5-1, the arrow with a number on the line represents the forward pointer, and that number is the span.
  • Back pointer: The back pointer of a node is marked with the word BW, which points to the previous node of the current node.
  • Points: 1.0, 2.0 and 3.0 of each node are the points saved by the node. In a skip list, the nodes are arranged in ascending order of the points they hold.
  • Member objects: O1, O2, and O3 of each node are the objects saved by the node.

Note that a header node is constructed the same as any other node: it also has a back pointer, a score, and a member object, but these attributes are not used, so the diagram omits them and shows only the layers of the header node.

5.1.1 Skip list nodes

The implementation of skiplist nodes is defined by the zskiplistNode structure:

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

5.1.1.1 layer

An array of layers in a skip list can contain multiple elements, each of which contains a pointer to another node. Programs can use these layers to speed up access to other nodes. In general, the more layers, the faster access to other nodes.

Each time a new jump 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 power law (larger numbers are less likely to occur).

The rule of random generation: the probability of occurrence decreases by half for each level raised

Int randomLevel() {int k=1; while (rand()%2) k++; k=(k<MAX_LEVEL)? k:MAX_LEVEL; return k; }Copy the code

5.1.1.2 Forward Pointers

Each layer has a forward pointer to the end of the table (the level[I].forward attribute) to access nodes from the head of the table to the end of the table.

  • The program first accesses the first node (the table header) and then moves from the forward pointer at the fourth level to the second node in the table.
  • On the second node, the program moves to the third node in the list following the forward pointer of the second layer.
  • At the third node, the program also follows the forward pointer to the second layer to the fourth node in the table
  • When the program reaches the fourth node, a NULL is encountered, and the program knows that it has reached the end of the skip list and terminates the loop.

5.1.1.3 span

The span of layer mainly records the distance between two nodes:

  • The greater the span between two nodes, the farther apart they are
  • All forward Pointers to NULL have a span of 0 because they are not connected to any nodes.

At first glance, it’s easy to think that span is related to traversal operations, but it’s not.

Traversal is done using only the forward pointer, and the span is actually used to calculate the rank: in the process of finding a node, the span of all the layers visited along the way is added up and the result is the rank of the target node in the skip list.

5.1.1.4 Backward pointer

The back pointer of a node is used to access a node from the end of the table to the head of the table. A forward pointer can skip multiple nodes at once, whereas our back pointer can only roll back one node at a time.

5.1.1.5 Points and members

The score attribute of a node is a floating-point number of type double, and all nodes in the skip list are sorted by score from smallest to largest.

The node’s member object (the obj property) is a pointer to a string object that holds an SDS value.

In the same skip list, each node must hold unique member objects, but each node can hold the same points: Nodes with the same score are sorted by the size of their member objects in lexicographical order, with nodes with smaller members coming first (near the head of the table) and nodes with larger members coming second (near the bottom of the table).

5.1.2 jump table

By holding these nodes in a Zskiplist structure, programs can easily process the entire skiplist, for example, quickly access the top and bottom nodes of the table, or quickly obtain the length of the skiplist.

The zskiplist structure is defined as follows:

Typedef struct zskiplist {// struct skiplistNode *header, *tail; Unsigned long length; Int level; int level; } zskiplist;Copy the code

The header and tail Pointers point to the head and tail nodes of the skip table, respectively. With these two Pointers, we can obtain the head and tail of the skip table by the time complexity of O(1).

By using the length attribute to record the number of nodes, the program can return the length of the skip list at O(1) complexity.

The level attribute is used to get the number of layers (excluding table headers) of the node with the largest number of jump layers at time O(1).

5.2 Skip list API

5.3 Key Reviews

  • Skip lists are one of the underlying implementations of ordered collections.
  • Redis’s skip list is implemented byzskiplist 和 zskiplistNodeTwo structures are composed of whichzskiplistProperty holds information about the skip table (such as head node, tail node, length), andzskiplistNodeUsed to represent skip list nodes.
  • The height of each skip list node is1 ~ 32Random number between.
  • In the same skip table, multiple nodes can contain the same score, but not the same objects.
  • Skip list nodes are sorted by the size of the points, and when the points are the same, the nodes are sorted by the size of the member objects.