一、題目

ZSet能用在哪些場景？跳表查找的過程，時間復雜度

二、ZSet 簡單使用

舉個例子，fruit-price 是一個有序集合鍵，這個有序集合以水果名為成員，水果價錢為分值，保存了 130 款水果的價錢：

redis>ZADD fruit-price 5 "banana"
redis>ZADD fruit-price 6.5 "cherry"
redis>ZADD fruit-price 8 "apple"


redis> ZRANGE fruit-price 0 2 WITHSCORES
1) "banana"
2) "5"
3) "cherry"
4) 6.5
5) "apple"
6) "8"

redis> ZCARD fruit-price
(integer)130

三、ZSet 結構

ZSet 結構即支持單個元素查詢，又支持范圍查詢，是如何實現的呢？

Redis 中有兩種數據結構來支持 ZSet 的功能，一個是字典 dict ，一個是 zskipList； 字典保存著從 member 到 score 的映射，跳躍表按 score 從小到大保存所有集合元素

先看下 ZSet 在代碼中的定義：

typedef struct zset {
   dict *dict;
   zskiplist *zsl;
} zset;

dict 各種編程語言中都有實現。可以保證 O(1) 的時間復雜度； 我們繼續看 zskiplist 的定義：

typedef struct zskiplist {
   struct zskiplistNode *header, *tail;
   unsigned long length;
   int level;
} zskiplist;

zskiplist 是 Redis 對 skiplist 做了變種，skiplist 就是我們常說的跳表；

四、跳躍表

跳躍表的特點

• 由許多層結構組成，每層都是一個有序鏈表
• 最底層的鏈表包含所有元素
• 如果一個元素出現在 level i 層的鏈表中，則它在 level i 之下的鏈表中也都會出現
• 每個節點包含兩個指針，一個指向同一鏈表中的下一個元素，一個指向下面一層的元素

查找過程

• 跳表的查找會從頂層鏈表的頭部元素開始遍歷該鏈表，直到找到元素大于或等于目標元素的節點，如果當前元素正好等于目標，那么就直接返回它；
• 如果當前元素大于目標或到達鏈表尾部，則移動到前一個節點的位置，然后垂直下降到下一層；
• 正因為 Skiplist 的搜索過程會不斷地從一層跳躍到下一層的，所以被稱為跳躍表；

舉例說明

假設鏈接包含 1-10，共 10 個元素。我們要找到第 9 個，需要從 header 遍歷，共 9 次才能找到：

一次只能比較一個數，最壞的情況下時間復雜度是 O(n)，如果我們一次可以比較 2 個元素就好了：

一次查找 2 個的話，我們只找了 5 次就找到了。所以就有了類似下面的結構，在鏈表上增加一層減少了元素個數的 “鏈表”：

如果增加兩層 “鏈表”，只查找 3 次就可以找到：

即便是我們找元素 8，也只需要遍歷 1 -> 4 -> 7 -> 8，共 4 次查詢；

這樣查找過程就非常類似于一個二分查找，使得查找的時間復雜度可以降低到 O(log n)

ZskipList 插入過程：

從上面 Skiplist 的創建和插入過程可以看出，每一個節點的層數（level）是隨機出來的，而且新插入一個節點不會影響其它節點的層數。 因此，插入操作只需要修改插入節點前后的指針，而不需要對很多節點都進行調整。這就降低了插入操作的復雜度

Redis 初始化的時候，只判斷存儲的元素長度是否大于 64 個字節。大于 64 個字節選擇 Zkiplist，否則 Ziplist。當執行增刪改查的方法，根據是 ziplist 還是 zkiplist 選擇不同的實現。只需要記住 zset，在兩種情況下使用 ziplist：

保存的元素個數不足 128 個；單個元素的大小超過 64 byte；

ziplist 編碼的有序集合使用緊挨在一起的壓縮列表節點來保存，第一個節點保存 member，第二個保存 score。ziplist 內的集合元素按 score 從小到大排序，score 較小的排在表頭位置

為什么采用跳躍表

• 跳表就是這樣的一種數據結構，結點是跳過一部分的，從而加快了查詢的速度。類似于 HashMap 中，Java 8 中當哈希沖突個數大于 7 個的時候，轉換為紅黑樹；
• 跳表跟紅黑樹兩者的算法復雜度差不多，為什么 Redis 要使用跳表而不使用紅黑樹呢？跳表相對于紅黑樹，代碼簡單；
• 如果我們要查詢一個區間里面的值，用平衡樹實現可能會麻煩。刪除一段區間時，如果是平衡樹，就會相當困難，畢竟涉及到樹的平衡問題，而跳表則沒有這種煩惱；

五、場景案例

1、信息統計

假設我們有某個班級所有學生的語文成績，想統計、查詢區間范圍、查詢單個學生成績、滿足高性能讀取這些需求， Redis 的 zset 結構無疑是最好的選擇。Redis 提供了豐富的 API。示例

ZADD yuwen 90 s01 89 s03 99 s02 74 s04 97 s05

以 yuwen 為 key 分別存儲了 s01 到 s06 共計 6 名學生的分數，我們可以查詢任一學生的成績：

ZSCORE yuwen s03

可以按照排序返回指定區間內的所有元素

ZRANGE yuwen 1 2 withscores

可以訪問指定分數區間內的所有元素

ZRANGEBYSCORE yuwen 90 100 withscores

可以統計指定區間內的個數

ZCOUNT yuwen 80 90

2、排行榜

• 經常瀏覽技術社區的話，應該對 “1小時最熱門” 這類榜單不陌生。如何實現呢？如果記錄在數據庫中，不太容易對實時統計數據做區分；
• 我們以當前小時的時間戳作為 zset 的 key，把貼子 ID 作為 member ，點擊數評論數等作為 score，當 score 發生變化時更新 score；
• 利用 ZREVRANGE 或者 ZRANGE 查到對應數量的記錄；