Redis ordered set object (Zset) uses ziplist and skiplist

The title first clarifies some basic common sense:

  • The five common data types in Redis: String (string), List (list), Hash (hash), Set (set), ZSet (ordered set), these five common data types essentially correspond to five Kind of objects , namely string objects, list objects, hash objects, collection objects, and ordered collection objects.
  • In Redis, any object has five attributes

[1] type ====> The type corresponds to the basic data type. For example, Redis_String corresponds to a string, Redis_List corresponds to a list
[2] encoding ====> encoding. The encoding method determines the underlying data structure of the object. There are at least two encoding methods for an object
[3] prt ====> pointer. Point to the data structure determined by the code, the data structure often contains stored data
[4] refcount ====> reference count. This attribute is mainly to implement the memory recovery mechanism in redis
[5] lru ====> least recently used. It is used to solve the idling time of the object, and it will also be used to delete what data should be deleted when the buffer reaches the maximum value and data is added to it.

Detailed Explanation of Orderly Combination (ZSet) Objects

As mentioned above, the underlying data structure of an object is determined by the encoding method of the object, and there are two encoding methods for ZSet

  • ziplist

  • See the book " Redis Design and Implementation " for the underlying implementation of the above two data structures of skiplist .
    Combine the underlying s in an orderly manner

ZipList

When using compressed tables, to ensure that the data in the collection is in order, the key is placed in the front one, and then the value corresponding to the key is placed in the back of the key. This will ensure the order of the collection.

Insert picture description here

SkipList

When using a jumping list, since the jumping list is originally ordered, you can use it directly.
For the data structure of the jump table, see " Redis Design and Implementation " P39

When an ordered collection object meets the following two conditions at the same time, the object uses compressed linked list encoding:

  • The number of elements stored in an ordered set is less than 128;
  • The length of all element members stored in the ordered set is less than 64 bytes;

If the above two conditions are not met, then ZipList will be converted to SkipList. At the same time, when the number of elements and the length of element members of the following SkipList meet the requirements, it will not fall back to ZipList.

Focus

When using SkipList to implement ZSet, the zset data structure pointed to by ptr contains a skiplist and dict structure. A mapping from SkipList object to score is created in the dict structure. The value corresponding to the key can be found with O(1) time complexity through dict.

So why not directly use a dictionary or skipList to implement Zset?

  • When using a dictionary directly, although the time complexity of querying key-value can be achieved O(1), the dictionary itself is unordered, and at least O(Nlog(N)) is required to sort.
  • When SkipList is used directly, although order can be achieved, querying key-value requires at least O(logN).