preface

< Redis design and Implementation >, as the saying goes, if you want to use something well, you must understand the content composition mechanism, so I took notes to understand the internal data structure.

Where Redis is used

  1. An ordered set
  2. Cluster nodes

Jump table

What is a skip list? A skip list is a data structure made up of

  1. List stores the entire contents of a skip list
  2. ListNode stores the contents of skip list nodes

The data structure

list

Skip list contains the following structures

  1. Header points to the skip table head node
  2. Tail Indicates the node at the end of the skip list
  3. Length indicates the number of nodes in the skip list, excluding the head node
  4. Level represents the maximum level value in a skip table node, excluding the head node

listNode

  1. The level [] array contains levels ranging from 1 to 32, and each level contains two attributes:
  • Forward: indicates the position of a node
  • Span Distance between the current node and a node
  1. Backward points to the previous node
  2. Score points
  3. Objects contained in obj (SSD string)

Figure said

conclusion

  1. Skip lists are one of the underlying implementations of ordered collections
  2. A Redis skip list is a list of two structures,listNode.
  3. The number of skip table node layers ranges from 1 to 32
  4. The scores in the skip list nodes can be the same but the object (obj) is unique
  5. Skip list nodes sort by the size of the score, and sort by the dictionary size of the object with the same score.

Take notes to reinforce your memory.