Skip lists

1.1 Introduction to Skip Lists 1.2 Implementation of Skip List Nodes 1.3 Implementation of Skip Lists

1.1 Introduction to skip lists

A skiplist is an ordered data structure that enables fast access to nodes by maintaining multiple Pointers to other nodes in each node. Skip lists support node look-up with average O(longN), worst O(N) complexity, and batch processing of nodes through sequential operations. Redis uses skip 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 the elements in the ordered set are long strings, Redis will use skip tables as the underlying implementation of ordered set keys.

1.2 Skip list node implementation

H /zskiplistNode and Redis. H /zskiplist. ZskiplistNode is used to represent the skiplist node, and zskiplist is used to store the related information of the skiplist node. Such as the number of nodes and points to the top and bottom of the table.

The diagram is a simple skip list

  • Header: Points to the table header node of the skip table.
  • Taiil: Points to the end node of a skip table.
  • Level: Records the current length of the skip table, that is, the number of nodes in the skip table (the head node is not counted).

In the figure above, the last four are the zskiplistNode structure, which contains the following properties:

  • Layer (level) : each layer of the node is marked with words L1, L2, L3, etc. L1 represents the first layer and L2 represents the second layer. Each layer has two properties: a forward pointer and a span.
  • Backwark pointer: A node’s backwark pointer is marked with BW, pointing to the node before the current node. The back pointer is used when the program traverses the table from the end to the head.
  • Score: 1.0, 2.0 and 3.0 in each node are the points saved by the node. In a skip list, the nodes are arranged in ascending order of points.
  • Member objects (OBJ) : O1, O2, and O3 in each node are the member objects held by the node.

1.2.1 Skip list nodes

The implementation of skip list nodes is defined by the following structure:

typedef struct zskiplistNode {
    // Back up the pointer
    struct zskiplistNode *backward;
    / / score
    double score;
    // Member objects
    robj *obj;
    / / layer
    struct zskiplistLevel {
        // Forward pointer
        struct zskiplistNode *forward;
        / / span
        unsigned int span;
    } level[];
}
Copy the code

1, the layer

The level array of skip list nodes can contain multiple elements, each of which contains a pointer to another node. Programs can access other nodes faster through these layers. In general, the more layers, the faster the access to other nodes. 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 power law (larger numbers are less likely to occur).

2. Forward Pointers

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

3, the span

The span of the layer (level[I].span property) is used to record 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 node.

4. Backward pointer

A node’s backward pointer (a backward attribute) is used to access a node from the end of the table to the head: unlike a forward pointer, where you can skip multiple nodes at once, since there is only one backward pointer per node, you can only go back to the previous node at a time.

5. Points and members

The score attribute of a node is a floating-point number of type double, and all nodes in a 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.

1.3 Skip list implementation

A skip list can be made up of just a few skip list nodes. As shown above. By using a Zskiplist structure to hold these nodes, the program can more easily process the entire skiplist, such as quickly accessing the top and bottom of the skiplist, or quickly obtaining information about the number of skiplist nodes (that is, the length of the skiplist).

The zskiplist structure is defined as follows:

typedef struct zskiplist {
    // Table header and table tail nodes
    struct zskiplistNode *head, *tail;
    // The number of nodes in the table
    unsigned long length;
    // The number of layers of the node with the largest middle level in the table
    int level;
} zskiplist;
Copy the code

1. The header and tail Pointers point to the head and tail of the skip table, respectively. By using these two Pointers, the program can quickly locate the head and tail of the skip table. 2. By using the length attribute to record the number of nodes, the program can return the length of the skip list in O(1) complexity. The level attribute is used to obtain the number of layers of the node with the highest height in the middle layer of the skip table in O(1) complexity. Note that the height of the top node is not counted.