Sorted Set (ZSet) 數(shù)據(jù)結(jié)構(gòu)

• Sorted Set (ZSet), 即有序集合, 底層使用 壓縮列表(ziplist) 或者 跳躍表(skiplist)

  1. 使用 壓縮列表(ziplist)
     當(dāng)同時(shí)滿足下面兩個(gè)條件時(shí),使用 ziplist 存儲(chǔ)數(shù)據(jù)
     • 元素個(gè)數(shù)少于128個(gè) (zset-max-ziplist-entries: 128)
     • 每個(gè)元素長度小于64字節(jié) (zset-max-ziplist-value: 64)
  2. 不滿足上面的條件, 使用 跳躍表(skiplist)
     • zset 在轉(zhuǎn)為 skiplist 之后，即使元素被逐漸刪除，也不會(huì)重新轉(zhuǎn)為 ziplist

• 有趣的命名: Sorted Set 為啥不縮寫為 SSet ? GitHub有人提問

  • Z代表XYZ中的Z, 所以有排序的意思(這個(gè)說法有點(diǎn)牽強(qiáng)吧)
  • Set命令已經(jīng)使用S作為前綴了, 所以Sorted Set不再使用S (可信度較高)
  • SSet 很奇怪, 很難發(fā)音 (這個(gè)理由也可以接受)

使用 ziplist 圖解

使用 skiplist 圖解

skiplist 定義

跳表是一種數(shù)據(jù)結(jié)構(gòu)。它使得包含n個(gè)元素的有序序列的查找和插入操作的平均時(shí)間復(fù)雜度都是 O(logn)，優(yōu)于數(shù)組的 O(n)復(fù)雜度。快速的查詢效果是通過維護(hù)一個(gè)多層次的鏈表實(shí)現(xiàn)的，且與下面一層鏈表元素的數(shù)量相比，每一層鏈表中的元素的數(shù)量更少。

skiplist 數(shù)據(jù)結(jié)構(gòu)

//跳躍表節(jié)點(diǎn)
typedef struct zskiplistNode {
    robj *obj; // 成員對象
    double score; // 分值
    struct zskiplistNode *backward; // 后退指針
    // 層
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前進(jìn)指針
        unsigned int span; // 跨度
    } level[];
} zskiplistNode;

//跳躍表
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
    unsigned long length; // 表中節(jié)點(diǎn)的數(shù)量
    int level; // 表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
} zskiplist;

//有序集合
typedef struct zset {
    dict *dict; // 字典，鍵為成員，值為分值, 用于支持 O(1) 復(fù)雜度的按成員取分值操作
    zskiplist *zsl; // 跳躍表，按分值排序成員, 用于支持平均復(fù)雜度為 O(log N) 的按分值定位成員操作, 以及范圍操作
} zset;

skiplist 圖解

簡單說下skiplist的查找過程:

比如查詢 分?jǐn)?shù)比 broadm 小的用戶名

1. 使用zset中的字典dict快速獲取broadm節(jié)點(diǎn)對應(yīng)的score=4
2. 從header節(jié)點(diǎn)的最高層(第5層)出發(fā),最高層(第5層)的前進(jìn)節(jié)點(diǎn)是 obj:mike score:3,對比發(fā)現(xiàn),此節(jié)點(diǎn)的score=3, 小于要查詢的節(jié)點(diǎn)的score=4 (說明目標(biāo)節(jié)點(diǎn)在此節(jié)點(diǎn)的右邊), 應(yīng)該繼續(xù)前進(jìn), 但是此節(jié)點(diǎn)沒有前進(jìn)節(jié)點(diǎn)了, 那就降低一層,直到找到有前進(jìn)節(jié)點(diǎn)的層為止(這里是第2層)
3. 第2層的前進(jìn)節(jié)點(diǎn)就是 broadm 了,找到了
4. 因?yàn)閟kiplist是有序的,并且每個(gè)節(jié)點(diǎn)都保存了 backward 指針, 所以直接遍歷鏈表就可以獲取分?jǐn)?shù)比broadm小的節(jié)點(diǎn)了

這里的數(shù)據(jù)量比較少,不容易看出來效果, 當(dāng)數(shù)據(jù)量很大的時(shí)候,這種查詢是非常高效的,平均時(shí)間復(fù)雜度為 O(logn),基本和平衡二叉樹等效

Redis使用skiplist而不是紅黑樹的原因?

• 紅黑樹實(shí)現(xiàn)細(xì)節(jié)過于復(fù)雜,比如為了保持平衡,需要做節(jié)點(diǎn)的旋轉(zhuǎn)操作, 而skiplist完全是靠隨機(jī)層數(shù)實(shí)現(xiàn)的自平衡,非常簡單
• 在范圍查找時(shí),跳躍表明顯優(yōu)于紅黑樹, 跳躍表是有序的鏈表,直接遍歷后繼節(jié)點(diǎn)即可, 而紅黑樹需要中序遍歷,復(fù)雜度更高

Sorted Set (ZSet) 常用命令

• ZADD key score member 添加一個(gè)或多個(gè)元素到集合中,如果已經(jīng)存在,則更新其score
• ZREM key member 刪除集合中的指定元素
• ZSCORE key member 獲取集合中指定元素的score
• ZRANK key member 獲取集合中指定元素的排名(從0開始)
• ZCARD key 獲取集合中元素的個(gè)數(shù)
• ZCOUNT key min max 統(tǒng)計(jì)score在閉區(qū)間[min,max]的元素的個(gè)數(shù)
• ZRANGE key min max 獲取指定排名范圍內(nèi)的元素
• ZDIFF, ZINTER, ZUNION 求多個(gè)集合的 差集,交集,并集