How to implement the internal implementation of ordered collections in Redis

Internal implementation of ordered collections

There are two internal implementations that can be used for ordered collections, namely compressed list (ziplist) and skip list (skiplist). Next, we will learn more about each in detail.

Use compressed list as internal implementation

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

Each set element consists of two compressed list nodes close together, where the first node saves the members of the element, and the second node saves the branch of the element. By arranging the elements in the compressed list together in order of score size, memory space usage can be effectively reduced.

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

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"

Using a jump table as the internal implementation

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

At this time, the ordered set actually contains two structures, one is a jump table and the other is a hash table.

In the jump list, 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 score saves the score of the element. Through jump tables, Redis can quickly perform score range, ranking and other operations on ordered sets.

In a hash table, a mapping from element members to element scores is created for an ordered set. In a key-value pair, the key is a string object and points to the element member, while the value holds the element's score. Through hash tables, Redis can quickly find the score of a specified element.

Although ordered sets use both jump tables and hash tables, both data structures use pointers to share members and scores in elements, without additional memory waste.

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

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"

Internally implemented conversion

When When an ordered set uses a compressed list as its internal implementation, and if a longer element member is added to the ordered set, or when there are too many elements in the ordered set, the ordered set will be converted to a jump. Table as internal implementation. Ordered sets using compressed lists as internal implementations do not convert to skip lists.

For example, we first create an ordered set with a compressed list as its internal implementation:

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"

Then, and then add an element with a longer member to it, it is converted to Jump list as internal implementation:

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"

Then, the element of the longer member is removed from the ordered set. The ordered set still uses jump list as internal implementation:

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"

The above is the detailed content of How to implement the internal implementation of ordered collections in Redis. For more information, please follow other related articles on the PHP Chinese website!