Shulou(Shulou.com)06/01 Report--

Most people do not understand the knowledge points of this article "how to achieve an ordered set in Redis", so the editor summarizes the following contents, detailed content, clear steps, and has a certain reference value. I hope you can get something after reading this article. Let's take a look at this "how to achieve the interior of an ordered set in Redis" article.

Internal implementation of ordered set

There are two internal implementations of ordered collections: compressed list (ziplist) and jump table (skiplist). Next, we will learn more about it in detail.

Using a compressed list as an internal implementation

When the number of elements in an ordered set is less than zset-max-ziplist-entries (the default is 128), and the length of each element member is less than zset-max-ziplist-value (the default is 64 bytes), a compressed list is used as the internal implementation of the ordered set.

Each collection element consists of two compressed list nodes next to each other, with the first node holding the members of the element and the second node holding the branches of the element. The elements in the compressed list are arranged next to each other according to the score from small to large, effectively reducing the use of memory space.

For example, we use the zadd command to create an ordered collection implemented with a compressed list:

127.0.0.1 two 6379 > zadd one-more-zset 1 one 2 two 3 three (integer) 3127.0.1 two 6379 > zrange one-more-zset 0-11) "one" 2) "two" 3) "three" 127.0.1 two 6379 > object encoding one-more-zset "ziplist" uses the jump table as the internal implementation

Use the jump table as the internal implementation of the ordered set when the number of elements in the ordered set is greater than or equal to zset-max-ziplist-entries (the default is 128), or when the length of each element member is greater than or equal to zset-max-ziplist-value (the default is 64 bytes).

At this point, there are actually two structures in the ordered set, one is the jump table and the other is the hash table.

In the jump table, all elements are arranged in order from small to large. The object pointer in the node of the jump table points to the string object of the element member, and the score holds the element's score. Through the jump table, Redis can quickly perform score range, ranking and other operations on ordered sets.

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

Although jump tables and hash tables are used in ordered set contracts, both data structures use pointers to share members and scores in elements, resulting in no additional memory waste.

For example, we use the zadd command to create an ordered collection implemented with a jump table:

127.0.0.1 zadd one-more-zset 6379 > integer 1 long-long-long-long-long-long-long-long-long-long-long-long-long-long (integer) 1127.0.0.1 integer 6379 > zrange one-more-zset 0-11) conversion within "long-long-long-long-long-long-long-long-long-long-long-long-long-long" 127.0.0.1 integer > object encoding one-more-zset "skiplist"

When an ordered set is implemented internally with a compressed list, and then a longer element member is added to the ordered set, or when there are too many elements to the ordered set, then the ordered set is converted to a jump table as the internal implementation. However, ordered collections with jump tables as internal implementations are not converted to compressed lists as internal implementations.

For example, let's first create an ordered collection with a compressed list as an internal implementation:

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

Then, add a longer member element to it, which is converted to a jump table as the internal implementation:

127.0.0.1 zadd one-more-zset 4 long-long-long-long-long-long-long-long-long-long-long-long-long-long (integer) 1127.0.0.1 integer 6379 > zrange one-more-zset 0-11) "one" 2) "two" 3) "three" 4) "long-long-long-long-long-long-long-long-long-long-long-long-long-long" 127.0.0.1 zrange one-more-zset "skiplist"

Then, the element of that longer member is removed from the ordered set, which is still implemented internally with a jump table:

127.0.0.1 zrem one-more-zset long-long-long-long-long-long-long-long-long-long-long-long-long-long (integer) 1127.0.0.1 zrange one-more-zset 0-11) "one" 2) "two" 3) "three" 127.0.0.1 two 6379 > object encoding one-more-zset "skiplist" these are the contents of the article "how to realize the interior of ordered sets in Redis" I believe we all have a certain understanding. I hope the content shared by the editor will be helpful to you. If you want to know more about the relevant knowledge, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.