今天我們說一下Redis中最后一個數(shù)據(jù)類型 “有序集合類型”，回首之前學(xué)過的幾個數(shù)據(jù)結(jié)構(gòu)，不知道你會不會由衷感嘆，開源的世界真好，寫這些代碼的好心人真的要一生平安哈，不管我們想沒想的到的東西，在這個世界上都已經(jīng)存在著，曾幾何時，我們想把所有數(shù)據(jù)按照數(shù)據(jù)結(jié)構(gòu)模式組成后灌輸?shù)絻?nèi)存中，然而為了達到內(nèi)存共享的方式，不得不將這塊內(nèi)存單獨部署，同時還要考慮怎么序列化，何時序列互的問題，煩心事太多太多。。。后來才知道有redis這么個玩意，能把高級的，低級的數(shù)據(jù)結(jié)構(gòu)單獨包裝到一個共享內(nèi)存中（Redis），高級的數(shù)據(jù)結(jié)構(gòu)，就是本篇所說的 “有序集合”。       

一： 有序集合（SortedSet）

　　 可能有些初次接觸SortedSet集合的人可能會說，這個集合的使用場景都有哪些？？？ 我可以明確的告訴你：“范圍查找“的天敵就是”有序集合“，任何大數(shù)據(jù)量下，查找一個范圍的時間復(fù)雜度永遠都是 O[(LogN)+M]，其中M：返回的元素個數(shù)。

　　 為了從易到難，我們還是先看一下redis手冊，挑選幾個我們常用的方法觀摩觀摩效果。。。 　

從上面17個命令中，毫無疑問，常用的命令為ZADD，ZREM，ZRANGEBYSCORE，ZRANGE。 

1. ZADD

ZADD key score member [[score member] [score member] ...]

將一個或多個 member 元素及其 score 值加入到有序集 key 當中。

　　這個是官方的解釋，賦值方式和hashtable差不多，只不過這里的key是有序的而已。下面我舉個例子：我有一個fruits集合，其中記錄了每個水果的price，然后我根據(jù)price的各種操作來獲取對應(yīng)的水果信息。

有了上面的基本信息，接下來我逐一送他們到SortedSet中，如下圖：

從上面的圖中，不知道你有沒有發(fā)現(xiàn)到什么異常？？？至少有兩種。

<1> 浮點數(shù)近似值的問題，比如grape，我在add的時候，寫明的是2.8，在redis中卻給我顯示近似值2.79999....，這個沒關(guān)系，本來就是這樣。

<2>  默認情況下，SortedSet是以key的升序排序的方式進行存放。 

2.  ZRANGE，ZREVRANGE

ZRANGE key start stop [WITHSCORES]

返回有序集 key 中，指定區(qū)間內(nèi)的成員。

其中成員的位置按 score 值遞增(從小到大)來排序。

  上面就是ZRange的格式模版，前面我在說ZAdd的時候其實我也已經(jīng)說了，但是這個不是重點，在說ZAdd的時候留下了一個問題就是ZRange默認是按照key升序排序的，對吧，那如果你想倒序顯示的話，怎么辦呢？？？其實你可以使用ZRange的鏡像方法ZREVRANGE 即可，如下圖： 

3. ZRANGEBYSCORE

ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]

返回有序集 key 中，所有 score 值介于 min 和 max 之間(包括等于 min 或 max )的成員。有序集成員按 score 值遞增(從小到大)次序排列。

 這個算是對SortedSet來說最最重要的方法了，文章開頭我也說了，有序集合最利于范圍查找，既然是查找，你得有條件對吧，下面我舉個例子： 

  <1>  我要找到1-4塊錢的水果種類，理所當然，我會找到【葡萄，蘋果】，如下圖：

 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> 

  <2>  我要找到1-4區(qū)間中最接近4塊的水果是哪個？？？ 這個問題就是要找到apple這個選項，那如果找到呢？？？ 仔細想想我可以這么做，

　  　   將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 中的一個或多個成員，不存在的成員將被忽略。

當 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樹“ 的思想一樣，用它來保持”樹“或者”鏈表”的平衡。
     詳細的我就不說了哈，不然的話又是一篇文章啦，如果非要了解的話，大家可以參見一下百度百科，我大概看了下百科里面畫的這張圖，就像下面這樣：

這幅圖中有三條鏈，在SkipList中是必須要保證每條鏈中的數(shù)據(jù)必須有序才可以，這是必須的。 

1. 如果要在level1層中找到節(jié)點6，那么你需要逐一遍歷，需要6次查找才能正確的找到數(shù)據(jù)。

2. 如果你在level2層中找到節(jié)點6的話，那么你需要4次才能找到。

3. 如果你在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;

從源碼中可以看出如下幾點：

<1>   zskiplistnode就是skiplist中的node節(jié)點，節(jié)點中有一個level[]數(shù)組，如果你夠聰明的話，你應(yīng)該知道這個level[]就是存放著上圖中
         的 level1，level2，level3 這三條鏈。 

<2>   level[]里面是zskiplistLevel實體，這個實體中有一個 *forward指針，這個指針就是指向同層中的后續(xù)節(jié)點。 

<3>   在zskiplistLevel中還有一個 robj類型的*obj指針，這個就是RedisObject對象哈，里面存放的就是我們的value值，接下來還有一個 score屬性，這個就是key值啦。。。skiplist就是根據(jù)它來進行排序的哈。 

<4>  接下來就是第二個枚舉zskiplist，這個沒什么意思，純粹的包裝層，比如里面的length是記錄skiplist中的節(jié)點個數(shù)，level記錄skiplist 當前的層數(shù)，用*header,*tail記錄skiplist中的首節(jié)點和尾節(jié)點。。。僅此而已。。。

最新評論