一、題目

ZSet能用在哪些場(chǎng)景？跳表查找的過程，時(shí)間復(fù)雜度

二、ZSet 簡(jiǎn)單使用

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

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)即支持單個(gè)元素查詢，又支持范圍查詢，是如何實(shí)現(xiàn)的呢？

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

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

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

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

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

zskiplist 是 Redis 對(duì) skiplist 做了變種，skiplist 就是我們常說(shuō)的跳表；

四、跳躍表

跳躍表的特點(diǎn)

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

查找過程

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

舉例說(shuō)明

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

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

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

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

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

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

ZskipList 插入過程：

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

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

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

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

為什么采用跳躍表

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

五、場(chǎng)景案例

1、信息統(tǒng)計(jì)

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

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

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

ZSCORE yuwen s03

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

ZRANGE yuwen 1 2 withscores

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

ZRANGEBYSCORE yuwen 90 100 withscores

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

ZCOUNT yuwen 80 90

2、排行榜

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

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

最新評(píng)論