面試官：Redis中有序集合的內部實現方式是什么？

面試官：Redis中基本的數據類型有哪些？

我：Redis的基本數據類型有：字符串（string）、哈希（hash）、列表（list）、集合（set）、有序集合（zset）。

面試官：有序集合的內部實現方式是什么？

我還沉浸在上一個問題的沾沾自喜中，頓時表情凝固了，手心開始冒出冷汗。“這個。。沒有太深入了解”，我支支吾吾的說到。

面試官：回去等消息吧。

這句話說的干凈利落，然后就沒有然后了。失敗是成功的媽媽，我不氣餒，決定馬上惡補一下。

有序集合的內部實現

有序集合的內部實現有兩種，分別是：壓縮列表（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中，有序集合的內部實現有壓縮列表（ziplist）和跳躍表（skiplist）兩種，當集合中的所有元素的成員長度較短并元素個數較少時，使用壓縮列表作為內部實現，否則使用跳躍表和哈希表作為內部實現。當條件不滿足時，壓縮列表可以轉換為跳躍表，但跳躍表不能轉換為壓縮列表。

竟然已經看到這里了，你我定是有緣人，留下你的和關注，他日必成大器。

Redis 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。