Interviewer: what is the internal implementation of ordered collection in redis?

interviewer ：Redis What are the basic data types in ？

I ：Redis The basic data types of are ： character string （string）、 Hash （hash）、 list （list）、 aggregate （set）、 Ordered set （zset）.

interviewer ： What is the internal implementation of an ordered set ？

I was also immersed in the complacency of the last question , Suddenly, his expression solidified , The palms began to sweat .“ This .. Not much in-depth understanding ”, I hesitated .

interviewer ： Go back and wait for the news .

This sentence is clear , And then there's no then . Failure is the mother of success , I'm not discouraged , Decided to mend it right away .

Internal implementation of ordered sets

There are two internal implementations of ordered sets , Namely ： Compressed list （ziplist） And the jump watch （skiplist）. Next , Let's have a detailed understanding of .

Take the compressed list as the internal implementation

When the number of elements in an ordered set is less than zset-max-ziplist-entries（ The default is 128 individual ）, And the length of each element member is less than zset-max-ziplist-value（ The default is 64 byte ） When , Use a compressed list as an internal implementation of an ordered set .

Each set element consists of two compressed list nodes next to each other , The first node holds the members of the element , The second node holds the branch of the element . The elements in the compressed list are arranged next to each other according to the score from small to large , Effectively reduce the use of memory space .

for instance , We use zadd Command to create an ordered collection implemented as a compressed list ：

Log in and copy

127.0.0.1:6379> zadd one-more-zset 1 one 2 two 3 three
(integer) 3
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
127.0.0.1:6379> object encoding one-more-zset
"ziplist"

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
      
8.
     

Take the jump table as the internal implementation

When the number of elements in an ordered set is greater than or equal to zset-max-ziplist-entries（ The default is 128 individual ）, Or the length of each element member is greater than or equal to zset-max-ziplist-value（ The default is 64 byte ） When , Use the jump table as the internal implementation of the ordered set .

here , In fact, there are two structures in an ordered set , One is the jump table , The other is the hash table .

In the jump table , All elements are arranged from small to large . In the node of the jump table object Pointer to the string object of the element member ,score Saved the score of the element . Through the jump table ,Redis You can quickly score and range ordered sets 、 Ranking and other operations .

In the hash table , A mapping from element members to element fractions is created for ordered collections . The key in the key value pair points to the string object of the element member , The value in the key value pair holds the score of the element . Through hash table ,Redis You can quickly find the score of the specified element .

Although ordered collections use both jump tables and hash tables , But both data structures use pointers to share members and scores in elements , No extra memory waste .

for instance , We use zadd Command to create an ordered set implemented by jump table ：

Log in and copy

127.0.0.1:6379> zadd one-more-zset 1 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-long"
127.0.0.1:6379> object encoding one-more-zset
"skiplist"

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
     

Internally implemented transformation

When an ordered set is implemented internally with a compressed list , Then add a longer element member to the ordered set , Or when there are too many elements in this ordered set , Then the ordered set will be transformed into an internal implementation with a jump table . however , An ordered set with a jump table as an internal implementation will not be converted to a compressed list as an internal implementation .

for instance , Let's first create an ordered collection with a compressed list as the internal implementation ：

Log in and copy

127.0.0.1:6379> zadd one-more-zset 1 one 2 two 3 three
(integer) 3
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
127.0.0.1:6379> object encoding one-more-zset
"ziplist"

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
      
8.
     

then , Add a longer member element to it , It is converted to take the jump table as the internal implementation ：

Log in and copy

127.0.0.1:6379> zadd one-more-zset 4 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) "one"
2) "two"
3) "three"
4) "long-long-long-long-long-long-long-long-long-long-long-long-long-long"
127.0.0.1:6379> object encoding one-more-zset
"skiplist"

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
      
8.
      
9.
     

then , Then remove the element of the longer member from the ordered set , An ordered set is still implemented internally with a jump table ：

Log in and copy

127.0.0.1:6379> zrem one-more-zset 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) "one"
2) "two"
3) "three"
127.0.0.1:6379> object encoding one-more-zset
"skiplist"

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
      
8.
     

summary

stay Redis in , The internal implementation of an ordered set has a compressed list （ziplist） And the jump watch （skiplist） Two kinds of , When the member length of all elements in the collection is short and the number of elements is small , Use a compressed list as an internal implementation , Otherwise, use the jump table and hash table as the internal implementation . When conditions are not met , The compressed list can be converted into a jump table , But the jump table cannot be converted to a compressed list .

---

I've seen it here , You and I must be predestined friends , Leave your give the thumbs-up and Focus on , It will become a great thing in the future .