一、題目

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 結(jié)構(gòu)

ZSet 結(jié)構(gòu)即支持單個元素查詢，又支持范圍查詢，是如何實現(xiàn)的呢？

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

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

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

dict 各種編程語言中都有實現(xiàn)?？梢员ＷC O(1) 的時間復雜度； 我們繼續(xù)看 zskiplist 的定義：

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

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

四、跳躍表

跳躍表的特點

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

查找過程

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

舉例說明

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

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

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

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

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

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

ZskipList 插入過程：

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

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

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

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

為什么采用跳躍表

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

五、場景案例

1、信息統(tǒng)計

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

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

以 yuwen 為 key 分別存儲了 s01 到 s06 共計 6 名學生的分數(shù)，我們可以查詢?nèi)我粚W生的成績：

ZSCORE yuwen s03

可以按照排序返回指定區(qū)間內(nèi)的所有元素

ZRANGE yuwen 1 2 withscores

可以訪問指定分數(shù)區(qū)間內(nèi)的所有元素

ZRANGEBYSCORE yuwen 90 100 withscores

可以統(tǒng)計指定區(qū)間內(nèi)的個數(shù)

ZCOUNT yuwen 80 90

2、排行榜

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

到此這篇關(guān)于Redis中ZSet的具體使用的文章就介紹到這了,更多相關(guān)Redis ZSet使用內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論