嘮一嘮Redis的有序集合

Redis ZSet實(shí)現(xiàn)

今天我們來看看Redis的zset。

zset是什么？首先顧名思義，zset包含單詞set，因此它肯定是滿足集合的性質(zhì)，即在zset中的元素不重復(fù)。

當(dāng)然要只用集合性質(zhì)，set就夠了。zset還有個(gè)特質(zhì)就是它是帶權(quán)重的集合。

比如對于熱搜這個(gè)情景下，我們可以往set中存熱搜的標(biāo)題，保證熱搜的標(biāo)題在集合中不重復(fù)，然后再搞個(gè)哈希表，鍵存儲熱搜標(biāo)題，值存儲當(dāng)前熱度。

要是我們首頁只能顯示10條熱搜，我們得挨個(gè)把這個(gè)哈希表讀下來，然后排序，獲得熱搜的top10。

復(fù)雜度略高，對于時(shí)間復(fù)雜度有沒有簡化？當(dāng)然可以，只要我們存儲這個(gè)熱搜標(biāo)題，按熱度存放就行了嘛，到時(shí)候順序讀取top10就完事。

嘿，那你可跟redis想一塊去了，zset就這么干的。

底層實(shí)現(xiàn)：跳表

在原始跳表的基礎(chǔ)上，redis做了點(diǎn)改進(jìn)，之前咱跳表是按值大小，現(xiàn)在變成權(quán)值大小，來看看它跳表節(jié)點(diǎn)定義：

typedef?struct?zskiplistNode?{
????sds?ele;//元素，在熱詞情景中，就變成了一段文字
????
????double?score;//權(quán)重值，熱詞情景下就是熱度

????struct?zskiplistNode?*backward;//指向后面的指針

????struct?zskiplistLevel?{
????????struct?zskiplistNode?*forward;
????????unsigned?long?span;
????}?level[];
????//節(jié)點(diǎn)的level數(shù)組，就是咱跳表上一講每個(gè)節(jié)點(diǎn)背后那一筐
}?zskiplistNode;

來結(jié)合上次的跳表的圖再理解一下。

非常好理解對不對。節(jié)點(diǎn)定義理清楚了，來看看redis跳表的定義：

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

屬性也很簡單，就是跳表頭節(jié)點(diǎn)，尾節(jié)點(diǎn)，長度和層數(shù)嘛。

來看看zset支持的操作：

1. zadd: 增加元素，如zadd mZySet 100 niu，添加元素niu，score為100
2. zcard: 查詢zset元素個(gè)數(shù)。
3. zrank: 獲取元素在zset的位置，如zrank mZySet niu，返回niu字段在zset的位置
4. zcount：獲取指定score之間存在的成員個(gè)數(shù)，如zcount 9 99，獲取在9到99元素個(gè)數(shù)，瞬間感覺是不是zset可以用來做成績錄入系統(tǒng)了對不對。
5. zrangebyscore：獲取指定score之間存在的成員。如zrangebyscore myZset 9 99獲取在9到99元素。
6. zrem：刪除元素，如zrem mZySet niu，刪除元素niu。
7. zscore: 獲取指定值分?jǐn)?shù)，如zscore mZySet niu

其他不常見api可以去redis官網(wǎng)獲取哈。

參考：

1. https://blog.csdn.net/helloworld_ptt/article/details/105801262
2. Redis設(shè)計(jì)與實(shí)現(xiàn)
3. Redis源碼剖析與實(shí)戰(zhàn)