[learning notes] the implementation principle of the ordered set Zset in redis - skip table

I was asked to assemble in an orderly way during the interview zset Implementation principle of , I thought it was based on red black tree , In fact, it is based on the jump table （skipList） Realized . This article mainly explains what is skip table , How does it find 、 To insert and delete elements , Compared with red and black trees, what are its advantages and disadvantages .

This article refers to the article redis Medium Zset principle .

1. Jump watch

(1) What is a jump watch

Jump list is a multi-layer ordered linked list . First consider a special case of table skipping , As shown in the figure below . From bottom to top, they are 1~4 layer , The first 1 Layer uses a linked list to store all elements in order , And then from the $i$ Every layer 1 Take one element to form the first $i+1$ Ordered linked list of layers , And add the second $i+1$ The layer linked list node points to the $i$ The pointer of the node corresponding to the layer . In this case , The first $i+1$ The number of nodes in the layer linked list is $i$ Half of the floor .

In practice , Each column is not divided into multiple linked list nodes , Instead, it looks like the following figure , A node corresponds to a column in the above figure , Set multiple pointers to the nodes below and to the right in a node . In this way, only increasing the pointer avoids the repeated storage of node values . It's just that this representation in the figure above is easier to understand .

(2) Jump table query

Or look at the picture above , If you want to search 46, Search from top to bottom .

• The first 4 layer ： Search from the beginning , find 55,46 Than 55 Small , So search from the position of the node to the next level ;
• The first 3 layer ： Search from the beginning , find 21,46 Than 21 Big , Continue to search and find 55,46 Than 55 Small , So from 21 Search down the level ;
• The first 2 layer ： from 21 Node search once , find 37,46 Than 37 Big , Continue to search and find 55,46 Than 55 Small , So from 37 Search down the level ;
• The first 1 layer ： from 37 Node search once , find 46, Just the node you are looking for , And has reached the bottom , End of the search .

You can find , The average time complexity of the search is O(log n), This is because every time you search on the upper level, the search scope is reduced by an average of half .

(3) Jump table insertion

When inserting elements , First find the location where you want to insert the element , Then insert . But if we adopt the above-mentioned method, we can start from $i$ Every layer 1 Take one element to form the first $i+1$ In the way of layer ordered linked list , It needs to be adjusted after insertion , It's a little bit of a hassle . So in the actual implementation , A random method is used to determine the height of the element to be inserted , That is to say 1 The layer must be inserted , Therefore, the minimum value of node height is 1, The node height is 2 The probability of is 0.5, The height is 3 The probability of is 0.25…… This ensures the $i+1$ The number of nodes in the layer linked list is about $i$ Half of the floor . The code of highly random algorithm is as follows ：

int random_level()  
{
    
    level = 1;
    #  Random generation 0 or 1, if 1 be level++, On the contrary, end the cycle 
    while(random(0,1))  
    {
    
        level++;
    }
    return level;  
}

More specifically , Similar to the process of query , From the top to the bottom, query the location of the new node to insert , If the height of the current layer is less than or equal to the height of the new node , Then insert . The average time complexity of the whole insertion is O(log n).

(4) Delete the skip table

Similar to the insert operation , I won't repeat

2. Contrast with red and black trees

Compared with red and black trees , The advantages of meter skipping are ：

• The query complexity is the same , All for O(log n)
• The time complexity of insertion and deletion is the same , All for O(log n), But red and black trees insert 、 It needs to be adjusted after deletion , The operation is more complicated , The skip table only needs to insert the adjacent nodes of the node
• Skip table is more suitable for range query , Just find the minimum value of the range , Then traverse in the first layer
• The overall implementation of the jump table is simpler than the red black tree