概述
- 在redis所支持的五種數據類型當中，zset是一個有序集合的實現，集合中的每個元素由成員對象member和分值score組成，整個有序集合按照分值score從小到大排序的，其中分值是可以重復的，而成員對象member是不能重復的。
- 有序集合zset在內部可以使用壓縮列表ziplist或者跳躍表skiplist來實現。
數據結構分析
一、壓縮列表
- 如果使用壓縮列表ziplist來實現，則鍵和分值緊湊相鄰保存在壓縮列表中，同時分值小的排在列表前面，分值大的排在列表后面。使用壓縮列表ziplist來保存需要滿足以下兩個條件，否則使用跳躍表skiplist：
- 集合元素少于128個；
- 集合每個元素的鍵和分值都少于64個字節；
- 即在集合元素較少，元素類型較小時，使用壓縮列表，這樣由于數據元素較少，故雖然壓縮列表效率較低，但是基本不會有多大影響，而且可以充分利用壓縮列表的連續內存和緊湊的數據結構實現來節省內存。
- 以上兩個條件可以在配置文件中分別通過zset-max-ziplist-entries和zset-max-ziplist-value這兩個參數來修改。
二、跳躍表與字典
- 源碼定義如下：
// 有序集合
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
- 如果是使用跳躍表skiplist，則會結合一個哈希字典dict來實現：
- 即使用哈希字典dict來保存鍵和分值的映射，實現O(1)復雜度獲取某個鍵的分值；通過跳躍表skiplist來根據分值排序來排序該集合，從而實現按分值排序，其中跳躍表的每個節點都同時包含分值和鍵。
- 在內存使用方面，哈希字典dict和跳躍表skiplist是通過指針來共享鍵和分值的，故不會存在兩份數據，節省了內存。
- 如果只使用哈希字典來實現，則獲取給定鍵對應的分值復雜度為O(1)，但是如果每次獲取有序集合，則需要獲取整個集合然后排序，需要O(NlogN)的時間復雜度和O(N)的空間復雜度。
- 如果只使用跳躍表skiplist來實現，則每次獲取某個鍵的分值都需要在跳躍表來查找，時間復雜度為O(logN)。
