Redis中ZSet的具體使用

2022-07-18 14:05:28

一、題目

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 查到對應數量的記錄；

到此這篇關於Redis中ZSet的具體使用的文章就介紹到這了,更多相關Redis ZSet使用內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！