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