1. 編碼

zset的編碼有ziplist和skiplist兩種。
底層分別使用ziplist(壓縮鏈表)和skiplist(跳表)實現。

• 什么時候使用ziplist什么時候使用skiplist？

當zset滿足以下兩個條件的時候，使用ziplist：

保存的元素少于128個 保存的所有元素大小都小于64字節

不滿足這兩個條件則使用skiplist。
(注意：這兩個數值是可以通過redis.conf的zset-max-ziplist-entries 和 zset-max-ziplist-value選項 進行修改。)

---

2. 實現

• ziplist編碼

關于什么是ziplist(壓縮鏈表)，可以參見這篇文章：Redis源碼分析-壓縮列表ziplist

ziplist 編碼的有序集合對象使用壓縮列表作為底層實現，每個集合元素使用兩個緊挨在一起的壓縮列表節點來保存，第一個節點保存元素的成員，第二個節點保存元素的分值。并且壓縮列表內的集合元素按分值從小到大的順序進行排列，小的放置在靠近表頭的位置，大的放置在靠近表尾的位置。

從小到大排列

ziplist結構

• skiplist編碼

skiplist 編碼的有序集合對象使用 zet 結構作為底層實現，一個 zset 結構同時包含一個字典和一個跳表：

typedef struct zset{ //跳躍表 zskiplist *zsl; //字典 dict *dice;} zset;

字典的鍵保存元素的值，字典的值則保存元素的分值；跳躍表節點的 object 屬性保存元素的成員，跳躍表節點的 score 屬性保存元素的分值。

這兩種數據結構會通過指針來共享相同元素的成員和分值，所以不會產生重復成員和分值，造成內存的浪費。

說明：其實有序集合單獨使用字典或跳躍表其中一種數據結構都可以實現，但是這里使用兩種數據結構組合起來，原因是假如我們單獨使用 字典，雖然能以 O(1) 的時間復雜度查找成員的分值，但是因為字典是以無序的方式來保存集合元素，所以每次進行范圍操作的時候都要進行排序；假如我們單獨使用跳躍表來實現，雖然能執行范圍操作，但是查找操作有 O(1)的復雜度變為了O(logN)。因此Redis使用了兩種數據結構來共同實現有序集合。

---

參考資料：

Redis詳解(五)------ redis的五大數據類型實現原理

Redis源碼分析-壓縮列表ziplist

作者：Katou_Megumi
鏈接：https://www.jianshu.com/p/e5a516831ac2
來源：簡書
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

總結

以上是生活随笔為你收集整理的底层实现_Redis有序集合zset的底层实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。