preface

This chapter introduces the basic usage and internal principles of SET and zset in Redis. Because these two data structures have a lot in common, I put them together in one chapter. And focus on a very important data structure inside Zset: skip list.

Basic introduction

set

Let’s take a look at set

A set in Redis is much like a HashSet in Java, with unordered, unique, and non-null key-value pairs.

> sadd books Java
(integer 1)
> sadd books Java
(integer 0)			# value the value is repeated
> sadd books Go
(integer 1)
> smembers books		# disorderly
1) "Go"
2) "Java"
Copy the code

zset

Zset is the most specific basic data structure in Redis, and the others are roughly equivalent to Java. It’s basically still a set but with a score attribute added to ensure order. Its internal implementation as skip lists will be highlighted later.

> zadd books 1 Java
(integer) 1
> zadd books 2 Go
(integer) 1
> zadd books 3 Python
(integer) 1
> zrange books 0 -1 	Take out in order by score
1) "Java"
2) "Go"
3) "Python"
Copy the code

In Zset score is of type double so sometimes we have problems with decimal accuracy.

When the last value in the zset is deleted, this and the zset are automatically deleted and the memory is reclaimed.

internals

Redis zset is a composite structure consisting of a hash and skiplist, where hash is used to store the correspondence between value and score, and skiplist is used to sort scores. For an internal implementation of Hash, see the previous article “Are you sure you don’t want to learn how Hash works in Redis”, where we focus on skiplist implementation.

Skiplist jump table

Because Zset requires efficient insertions and deletions, the underlying implementation of an array is not suitable, and the structure of a linked list is needed. When inserting new elements, insert them to appropriate positions in the linked list according to score to ensure the order of the linked list. The efficient way is to find the insertion point by binary search.

So the problem comes, binary search objects must be ordered array, only array support fast location, linked list can not do how to do? This is where skip lists come in.

As shown in the figure, the concept of level L0~L3 is added to the skip list on the basis of linked list. The skip list of Redis has 64 layers, which can be accommodatedThe level of each element is randomly assigned, with a 100% probability of L0, meaning that each element has at least one level. There’s a 50% chance of L1, 25% chance of L2, and so on.

The structure corresponding to each KV is ZSLNode. Pointers are used between kV to form an ordered bidirectional linked list. Kv’s of the same tier will be linked together using Pointers. Each layer is traversed from the kv header, the skipper’s header pointer.

Header structure is also zslNode, where value is null,score is Double.MIN_VALUE is the first.

struct zslnode{
    string value;
    double score;
    zslnode*[] forwards;	// A pointer to a multilevel connection
    zslnode* backward;		// backtrace pointer
}

struct zsl{
    zslnode* header;			// Skip header pointer
    int maxLevel;				// The highest level of the current node
    map<String,zslnode*> ht;	// Key-value pairs in hash
}
Copy the code

To find the

Now that we’ve introduced Skiplist’s data structures, let’s look at how Skiplist can quickly locate elements.

In the figure above, suppose we want to find the node 3. Skiplist will start at the top of the header and find the first element that is smaller than the target element one level down until it reaches the bottom and finds the node 3 as follows:

  1. L3:header -> 4 -> header
  2. L2:header -> 2 -> 4 -> 2
  3. L1: 2 -> 4 ->2
  4. L0: 2 -> 3

Description:

  1. If 4 is larger than 3, go back to the header and drop one layer
  2. L2 layer header to find 2 smaller than 3 * * * *, continue to traverse to find 4, back to 2 at the same time drop a layer
  3. L1 layer 2 find 4 is larger than 3, go back to 2 and drop one layer
  4. L0 layer 2 finds 3 desired nodes

The time complexity of the algorithm in the whole search process is.