This article is from Huawei cloud community “5 minutes to understand the internal implementation of Redis skiplist”, by Wanmo Society.

A skiplist is an ordered data structure that provides quick access to a given node by maintaining different levels of Pointers to subsequent nodes at each node. The average time complexity is O(log n) and the worst time complexity is O(n).

Redis uses skiplist as one of the underlying implementations of ordered sets (Zsets). Internal implementations of ordered collections use skip lists and hash tables when the number of ordered collections is greater than or equal to zset-max-ziplist-entries (128 by default), or when each element member is greater than or equal to zset-max-ziplist-value (64 bytes by default).

For example, we use the zadd command to create an ordered collection implemented as a skip list:

127.0.0.1:6379> zadd one-more-zset 1 long-long-long-long-long-long-long-long-long-long-long-long-long-long-long-long (integer) 1 127.0.0.1:6379> zrange one-more-zset 0-1 1) "long-long-long-long-long-long-long-long-long-long-long-long-long" 127.0.0.1:6379> Object encoding one-more-zset "skiplist"Copy the code

Implementation of skip lists

Skip lists in Redis are represented by the Zskiplist structure, which contains a bidirectional linked list of multiple skiplist nodes, each of which holds element members and corresponding minutes. Let’s take a closer look at them one by one.

Zskiplist structure

Skip lists are represented by the Zskiplist structure, which contains the following properties:

  • headerProperty: Pointer to the head skip list node.
  • tailProperty: pointer to a trailing skip list node.
  • levelProperty: Indicates the number of layers of the node with the largest number of layers in the skip table. The number of layers of the top node is not counted.
  • lengthProperty: Represents the total number of nodes in a skip list.

Structure of skip list nodes

Skip list nodes are represented using the zskiplistNode structure, which contains the following properties:

  • levelProperty: Represents an array of layers used by each item in the arrayzskiplistLevelStructure representation, which contains the following two properties:
    • forwardProperty: Pointers to other nodes at the end of the table.
    • spanProperty: current node toforwardHow many nodes does the node point to span?
  • backwardProperty: A pointer to the previous node of the current node.
  • objAttribute: A pointer to an element member.
  • scoreAttribute: The score corresponding to the current element member.

Graphic skip list

Let’s give you an example:

This is the internal structure of a skip list, which has four elements, the keys are: million, cat, learn, society.

Why not use a balanced tree?

Skip lists store elements in a hierarchical linked list in an orderly fashion. In most cases, skip lists are as efficient as balanced trees, finding, deleting, adding, and so on can be done in logarithmic expected time, and are much simpler and more intuitive to implement than balanced trees. So instead of using a balance tree in Redis, skip lists are used.

Click to follow, the first time to learn about Huawei cloud fresh technology ~