Sorted Set (ZSet) 數據結構 Sorted Set (ZSet), 即有序集合, 底層使用 壓縮列表(ziplist) 或者 跳躍表(skiplist) 使用 壓縮列表(ziplist) 當同時滿足下麵兩個條件時,使用 ziplist 存儲數據 元素個數少於128個 (zset-ma ...
Sorted Set (ZSet) 數據結構
-
Sorted Set (ZSet), 即有序集合, 底層使用 壓縮列表(ziplist) 或者 跳躍表(skiplist)
-
有趣的命名: Sorted Set 為啥不縮寫為 SSet ? GitHub有人提問
- Z代表XYZ中的Z, 所以有排序的意思(這個說法有點牽強吧)
- Set命令已經使用S作為首碼了, 所以Sorted Set不再使用S (可信度較高)
- SSet 很奇怪, 很難發音 (這個理由也可以接受)
使用 ziplist 圖解
使用 skiplist 圖解
skiplist 定義
跳錶是一種數據結構。它使得包含n個元素的有序序列的查找和插入操作的平均時間複雜度都是 O(logn)，優於數組的 O(n)複雜度。快速的查詢效果是通過維護一個多層次的鏈表實現的，且與下麵一層鏈表元素的數量相比，每一層鏈表中的元素的數量更少。
skiplist 數據結構
//跳躍表節點
typedef struct zskiplistNode {
robj *obj; // 成員對象
double score; // 分值
struct zskiplistNode *backward; // 後退指針
// 層
struct zskiplistLevel {
struct zskiplistNode *forward; // 前進指針
unsigned int span; // 跨度
} level[];
} zskiplistNode;
//跳躍表
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 表頭節點和表尾節點
unsigned long length; // 表中節點的數量
int level; // 表中層數最大的節點的層數
} zskiplist;
//有序集合
typedef struct zset {
dict *dict; // 字典，鍵為成員，值為分值, 用於支持 O(1) 複雜度的按成員取分值操作
zskiplist *zsl; // 跳躍表，按分值排序成員, 用於支持平均複雜度為 O(log N) 的按分值定位成員操作, 以及範圍操作
} zset;
skiplist 圖解
簡單說下skiplist的查找過程:
比如查詢 分數比 broadm 小的用戶名
- 使用zset中的字典dict快速獲取broadm節點對應的score=4
- 從header節點的最高層(第5層)出發,最高層(第5層)的前進節點是 obj:mike score:3,對比發現,此節點的score=3, 小於要查詢的節點的score=4 (說明目標節點在此節點的右邊), 應該繼續前進, 但是此節點沒有前進節點了, 那就降低一層,直到找到有前進節點的層為止(這裡是第2層)
- 第2層的前進節點就是 broadm 了,找到了
- 因為skiplist是有序的,並且每個節點都保存了 backward 指針, 所以直接遍歷鏈表就可以獲取分數比broadm小的節點了
這裡的數據量比較少,不容易看出來效果, 當數據量很大的時候,這種查詢是非常高效的,平均時間複雜度為 O(logn),基本和平衡二叉樹等效
Redis使用skiplist而不是紅黑樹的原因?
- 紅黑樹實現細節過於複雜,比如為了保持平衡,需要做節點的旋轉操作, 而skiplist完全是靠隨機層數實現的自平衡,非常簡單
- 在範圍查找時,跳躍表明顯優於紅黑樹, 跳躍表是有序的鏈表,直接遍歷後繼節點即可, 而紅黑樹需要中序遍歷,複雜度更高
Sorted Set (ZSet) 常用命令
- ZADD key score member 添加一個或多個元素到集合中,如果已經存在,則更新其score
- ZREM key member 刪除集合中的指定元素
- ZSCORE key member 獲取集合中指定元素的score
- ZRANK key member 獲取集合中指定元素的排名(從0開始)
- ZCARD key 獲取集合中元素的個數
- ZCOUNT key min max 統計score在閉區間[min,max]的元素的個數
- ZRANGE key min max 獲取指定排名範圍內的元素
- ZDIFF, ZINTER, ZUNION 求多個集合的 差集,交集,並集
