對 Redis 中的有序集合 SortedSet 的理解
本篇說一下Redis中的 有序集合類型,曾幾何時,我們想把所有數(shù)據(jù)存到內(nèi)存中的 數(shù)據(jù)結(jié)構(gòu)中,但為了多機器共享內(nèi)存,不得不將這塊內(nèi)存包裝成wcf單獨部署,同時還要考慮怎么序列化,煩心事太多太多。。。后來才知道有redis這么🐂👃的東西,能把高級的,低級的數(shù)據(jù)結(jié)構(gòu)單獨包裝到一個共享內(nèi)存中。
一:有序集合(SortedSet)
可能有些初次接觸SortedSet集合的朋友可能會說,這個集合的使用場景都有哪些???我可以明確的告訴你:范圍查找 的天敵就是有序集合,任何大數(shù)據(jù)量下,查找一個范圍的時間復(fù)雜度永遠(yuǎn)都是 O[(LogN)+M],其中M:返回的元素個數(shù),為了從易到難,我們還是先看一下redis手冊,挑選幾個我們常用的方法觀摩觀摩效果。
從上面的17個命令中,毫無疑問,常用的命令為ZADD,ZREM,ZRANGEBYSCORE,ZRANGE。
1. ZADD
ZADD key score member [[score member] [score member] ...]將一個或多個 member 元素及其 score 值加入到有序集 key 當(dāng)中。
這個是官方的解釋,賦值方式和hashtable差不多,只不過這里的key是有序的而已。下面我舉個例子:我有一個fruits集合,其中記錄了每個水果的price,然后我根據(jù)price的各種操作來獲取對應(yīng)的水果信息。
有了上面的基本信息,接下來我逐一送他們到SortedSet中,如下圖:
從上面的圖中,不知道你有沒有發(fā)現(xiàn)到什么異常???至少有兩種。
- 浮點數(shù)近似值的問題,比如grape,我在add的時候,寫明的是2.8,在redis中卻給我顯示近似值2.79999....,這個沒關(guān)系,本來就是這樣。
- 默認(rèn)情況下,SortedSet是以key的升序排序的方式進行存放。
2. ZRANGE,ZREVRANGE
ZRANGE key start stop [WITHSCORES]
返回有序集 key 中,指定區(qū)間內(nèi)的成員。
其中成員的位置按 score 值遞增(從小到大)來排序。
上面就是ZRange的格式模版,前面我在說ZAdd的時候其實我也已經(jīng)說了,但是這個不是重點,在說ZAdd的時候留下了一個問題就是ZRange,默認(rèn)是按照key升序排序的, 對吧,那如果你想倒序顯示的話,怎么辦呢???其實你可以使用ZRange的鏡像方法ZREVRANGE 即可,如下圖:
3. ZRANGEBYSCORE
- ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]
- 返回有序集 key 中,所有 score 值介于 min 和 max 之間(包括等于 min 或 max )的成員。有序集成員按 score 值遞增(從小到大)次序排列。
這個算是對SortedSet來說最最重要的方法了,文章開頭我也說了,有序集合最利于范圍查找,既然是查找,你得有條件對吧,下面我舉個例子:
我要找到1-4塊錢的水果種類,理所當(dāng)然,我會找到 葡萄,蘋果,如下圖:
- 127.0.0.1:6379> zrangebyscore fruits 1 4 withscores
- 1) "grape"
- 2) "2.7999999999999998"
- 3) "apple"
- 4) "3.5"
- 127.0.0.1:6379>
我要找到1-4區(qū)間中最接近4塊的水果是哪個???這個問題就是要找到apple這個選項,那如果找到呢???仔細(xì)想想我可以這么做,將1-4區(qū)間中的所有數(shù)倒序再取第一條數(shù)據(jù)即可,對吧,如下代碼。
- 127.0.0.1:6379> zrevrangebyscore fruits 4 1 withscores
- 1) "apple"
- 2) "3.5"
- 3) "grape"
- 4) "2.7999999999999998"
- 127.0.0.1:6379> zrevrangebyscore fruits 4 1 withscores limit 0 1
- 1) "apple"
- 2) "3.5"
- 127.0.0.1:6379>
4. ZREM
- ZREM key member [member ...]
- 移除有序集 key 中的一個或多個成員,不存在的成員將被忽略。
- 當(dāng) key 存在但不是有序集類型時,返回一個錯誤。
跟其他方法一樣,zrem的目的就是刪除指定的value成員,比如這里我要刪除scores=3.5 的 apple記錄。
- 127.0.0.1:6379> zrem fruits apple
- (integer) 1
- 127.0.0.1:6379> zrange fruits 0 -1 withscores
- 1) "grape"
- 2) "2.7999999999999998"
- 3) "pear"
- 4) "4.0999999999999996"
- 5) "banana"
- 6) "5"
- 7) "nut"
- 8) "9.1999999999999993"
- 127.0.0.1:6379>
你會發(fā)現(xiàn),已經(jīng)沒有apple的相關(guān)記錄了,因為已經(jīng)被我刪除啦。。。
二:探索原理
簡單的操作都已經(jīng)演示完畢了,接下來探討下sortedset到底是由什么數(shù)據(jù)結(jié)構(gòu)支撐的,大家應(yīng)該早有耳聞,sortedset在CURD的攤還分析上都是Log(N)的復(fù)雜度,可以與平衡二叉樹媲美,它就是1987年才出來的新型高效數(shù)據(jù)結(jié)構(gòu)跳躍表(SkipList),SkipList牛逼的地方在于跳出了樹模型的思維,用多層鏈表的模式構(gòu)造了Log(N)的時間復(fù)雜度,層的高度增加與否,采用隨機數(shù)的模式,這個和 Treap樹 的思想一樣,用它來保持樹或者鏈表的平衡。
詳細(xì)的我就不說了哈,不然的話又是一篇文章啦,如果非要了解的話,大家可以參見一下百度百科:http://baike.baidu.com/link?url=I8F7T W933ZjIeBea_-dW9KeNsfKXMni0IdwNB10N1qnVfrOh_ubzcUpgwNVgRPFw3iCkhewGaYjM_o51xchS8a
我大概看了下百科里面畫的這張圖,就像下面這樣:
這幅圖中有三條鏈,對吧,在SkipList中是必須要保證每條鏈中的數(shù)據(jù)必須有序才可以,這是必須的。
- 如果要在level1層中找到節(jié)點6,那么你需要逐一遍歷,需要6次查找才能正確的找到數(shù)據(jù)。
- 如果你在level2層中找到節(jié)點6的話,那么你需要4次才能找到。
- 如果你在level3層中找到節(jié)點6的話,那么你需要3次就可以找到。。。。
現(xiàn)在宏觀理解上,是不是有一種感覺,如果level的層數(shù)越高,相對找到數(shù)據(jù)需要遍歷的次數(shù)就越少,對吧,這就是跳躍表的思想,不然怎么跳哈,接下來我們來看看redis中是怎么定義這個skiplist的,它的源碼在redis.h 中:
- /* ZSETs use a specialized version of Skiplists */
- 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;
從源碼中可以看出如下幾點:
- zskiplistnode就是skiplist中的node節(jié)點,節(jié)點中有一個level[]數(shù)組,如果你夠聰明的話,你應(yīng)該知道這個level[]就是存放著上圖中的 level1,level2,level3 這三條鏈。
- level[]里面是zskiplistLevel實體,這個實體中有一個 *forward指針,這個指針就是指向同層中的后續(xù)節(jié)點。
- 在zskiplistLevel中還有一個 robj類型的*obj指針,這個就是RedisObject對象哈,里面存放的就是我們的value值,接下來還有一個score屬性,這個就是key值啦。。。skiplist就是根據(jù)它來進行排序的哈。
- 接下來就是第二個枚舉zskiplist,這個沒什么意思,純粹的包裝層,比如里面的length是記錄skiplist中的節(jié)點個數(shù),level記錄skiplist當(dāng)前的層數(shù),用*header,*tail 記錄 skiplist 中的首節(jié)點和尾節(jié)點。。。僅此而已。。。
本文轉(zhuǎn)載自微信公眾號「 一線碼農(nóng)聊技術(shù)」,可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系 一線碼農(nóng)聊技術(shù)公眾號。