Redis中有序集合的內部如何實現

有序集合的內部實作

有兩種內部實作方式可以用於有序集合，分別是壓縮列表（ziplist）和跳躍表（skiplist）。接下來，我們分別進行詳細的了解。

以壓縮列表作為內部實作

當有序集合的元素個數小於zset-max-ziplist-entries（預設為128個），而每個元素成員的長度小於zset-max-ziplist-value（預設為64位元組）的時候，使用壓縮列表作為有序集合的內部實作。

每個集合元素由兩個緊挨著的兩個壓縮列表結點組成，其中第一個結點保存元素的成員，第二個結點保存元素的分支。透過按照分數的大小順序將壓縮列表中的元素依序排列在一起，可以有效地減少記憶體空間的使用。

舉個例子，我們使用zadd指令建立一個以壓縮列表為實現的有序集合：

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"

以跳躍表作為內部實作

當有序集合的元素個數大於等於zset-max-ziplist-entries（預設為128個），或每個元素成員的長度大於等於zset-max-ziplist-value（預設為64位元組）的時候，使用跳躍表作為有序集合的內部實現。

此時，在有序集合中其實包含了兩個結構，一個是跳躍表，另一個是哈希表。

在跳躍表中，所有元素都依照從小到大的順序排列。跳躍表的結點中的object指標指向元素成員的字串對象，score保存了元素的分數。透過跳躍表，Redis可以快速地對有序集合進行分數範圍、排名等操作。

在雜湊表中，為有序集合建立了一個從元素成員到元素分數的對應。在鍵值對中，鍵是字串物件並指向元素成員，而值則保存了元素的分數。透過哈希表，Redis可以快速找到指定元素的分數。

雖然有序集合同時使用跳躍表和雜湊表，但是這兩個資料結構都使用指標共享元素中的成員和分數，不會額外的記憶體浪費。

舉個例子，我們使用zadd指令來建立一個以跳躍表為實現的有序集合：

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"

內部實作的轉換

當一個有序集合是以壓縮列表作為內部實現時，再向這個有序集合添加較長的元素成員，或向這個有序集合的元素個數過多時，那麼這個有序集合就會轉換為以跳躍表作為內部實現。使用壓縮列表作為內部實現的有序集合不會轉換為跳躍表。

舉個例子，我們先創建一個以壓縮列表作為內部實現的有序集合：

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"

然後，再向它添加一個較長成員的元素，它就是轉換為以跳躍表作為內部實現：

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"

然後，再把那一個較長成員的元素從有序集合中移除，有序集合依然是以跳躍表作為內部實現：

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"

以上是Redis中有序集合的內部如何實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！