Zset原理
有序集合對象是有序的。與列表使用索引下標作為排序依據不同铲觉，有序集合為每個元素設置一個分數(shù)（score）作為排序依據
ZSet底層如何實現(xiàn)
一森缠、使用ziplist祝闻。
前提：保存元素數(shù)量小于128，并且每個元素長度小于64字節(jié)
（這兩個參數(shù)可以通過zset-max-ziplist-entries 選項和 zset-max-ziplist-value 進行修改）-
ziplist原理：
壓縮列表（ziplist）是Redis為了節(jié)省內存而開發(fā)的甘苍，是由一系列特殊編碼的連續(xù)內存塊組成的順序型數(shù)據結構尝蠕，一個壓縮列表可以包含任意多個節(jié)點（entry），每個節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值载庭。image
- 每個節(jié)點組成如圖看彼。previous_entry_length保存前一個節(jié)點的長度，遍歷時可根據定位到前一個節(jié)點囚聚。encoding存儲content的類型和長度闲昭。content保存節(jié)點的內容
二、使用字典和跳躍表
typedef struct zset{
//跳躍表
zskiplist *zsl;
//字典
dict *dice;
} zset;
字典的鍵保存元素的值靡挥，字典的值則保存元素的分值序矩；跳躍表節(jié)點的 object 屬性保存元素的值，跳躍表節(jié)點的 score 屬性保存元素的分值跋破。
為什么不直接用跳躍表
假如我們單獨使用 字典簸淀，雖然能以 O(1) 的時間復雜度查找成員的分值，但是因為字典是以無序的方式來保存集合元素毒返，所以每次進行范圍操作的時候都要進行排序租幕；假如我們單獨使用跳躍表來實現(xiàn)，雖然能執(zhí)行范圍操作拧簸，但是查找操作有 O(1)的復雜度變?yōu)榱薕(logN)劲绪。因此Redis使用了兩種數(shù)據結構來共同實現(xiàn)有序集合。
字典
字典中的鍵是唯一的，可以通過key來查找值
-
字典底層實現(xiàn)是哈希表贾富，字典有兩個哈希表歉眷，一個在擴容時使用，哈希表擴容使用漸進式擴容颤枪，發(fā)送擴容時需要在兩個哈希表中進行搜索汗捡。
image 發(fā)生哈希沖突時使用鏈地址法解決
跳躍表
跳躍表（skiplist）是一種有序數(shù)據結構，它通過在每個節(jié)點中維持多個指向其它節(jié)點的指針畏纲，從而達到快速訪問節(jié)點的目的扇住。
- 性質
- 由很多層結構組成
- 每一層都是一個有序的鏈表，排列順序為由高層到底層盗胀，都至少包含兩個鏈表節(jié)點艘蹋，分別是前面的head節(jié)點和后面的nil節(jié)
- 最底層的鏈表包含了所有的元素
- 如果一個元素出現(xiàn)在某一層的鏈表中，那么在該層之下的鏈表也全都會出現(xiàn)（上一層的元素是當前層的元素的子集）
- 鏈表中的每個節(jié)點都包含兩個指針票灰，一個指向同一層的下一個鏈表節(jié)點女阀，另一個指向下一層的同一個鏈表節(jié)點；
- 定義
typedef struct zskiplistNode {
//層
struct zskiplistLevel{
//前進指針
struct zskiplistNode *forward;
//跨度
unsigned int span;
}level[];
//后退指針
struct zskiplistNode *backward;
//分值
double score;
//成員對象
robj *obj;
} zskiplistNode
typedef struct zskiplist{
//表頭節(jié)點和表尾節(jié)點
structz skiplistNode *header, *tail;
//表中節(jié)點的數(shù)量
unsigned long length;
//表中層數(shù)最大的節(jié)點的層數(shù)
int level;
}zskiplist;
- 操作
- 搜索：從最高層的鏈表節(jié)點開始米间，如果比當前節(jié)點要大和比當前層的下一個節(jié)點要小强品，那么則往下找膘侮，也就是和當前層的下一層的節(jié)點的下一個節(jié)點進行比較屈糊，以此類推，一直找到最底層的最后一個節(jié)點琼了，如果找到則返回逻锐，反之則返回空。
- 插入：首先確定插入的層數(shù)雕薪，有一種方法是假設拋一枚硬幣昧诱，如果是正面就累加，直到遇見反面為止所袁，最后記錄正面的次數(shù)作為插入的層數(shù)盏档。當確定插入的層數(shù)k后，則需要將新元素插入到從底層到k層燥爷。
- 刪除：在各個層中找到包含指定值的節(jié)點蜈亩，然后將節(jié)點從鏈表中刪除即可，如果刪除以后只剩下頭尾兩個節(jié)點前翎，則刪除這一層稚配。
