# 有序集
[TOC=2,3]
`REDIS_ZSET` (有序集)是 [ZADD](http://redis.readthedocs.org/en/latest/sorted_set/zadd.html#zadd "(in Redis 命令參考 v2.8)") 、 [ZCOUNT](http://redis.readthedocs.org/en/latest/sorted_set/zcount.html#zcount "(in Redis 命令參考 v2.8)") 等命令的操作對象,它使用 `REDIS_ENCODING_ZIPLIST` 和 `REDIS_ENCODING_SKIPLIST` 兩種方式編碼:
![digraph redis_zset { node [shape=plaintext, style = filled]; edge [style = bold]; // type REDIS_ZSET [label="有序集合\nREDIS_ZSET", fillcolor = "#95BBE3"]; // encoding REDIS_ENCODING_ZIPLIST [label="ziplist\nREDIS_ENCODING_ZIPLIST", fillcolor = "#FADCAD"]; REDIS_ENCODING_SKIPLIST [label="跳躍表\nREDIS_ENCODING_SKIPLIST", fillcolor = "#FADCAD"]; // edge REDIS_ZSET -> REDIS_ENCODING_ZIPLIST; REDIS_ZSET -> REDIS_ENCODING_SKIPLIST; // datastruct 1 ziplist [label="ziplist"]; REDIS_ENCODING_ZIPLIST -> ziplist; // datastruct 2 zset [label="redis.h/zset"]; dict [label="dict.h/dict"]; zskiplist [label="redis.h/zskiplist"]; REDIS_ENCODING_SKIPLIST -> zset; zset -> dict; zset -> zskiplist;}](https://box.kancloud.cn/2015-09-13_55f4effcf0888.svg)
### 編碼的選擇
在通過 [ZADD](http://redis.readthedocs.org/en/latest/sorted_set/zadd.html#zadd "(in Redis 命令參考 v2.8)") 命令添加第一個元素到空 `key` 時,程序通過檢查輸入的第一個元素來決定該創建什么編碼的有序集。
如果第一個元素符合以下條件的話,就創建一個 `REDIS_ENCODING_ZIPLIST` 編碼的有序集:
- 服務器屬性 `server.zset_max_ziplist_entries` 的值大于 `0` (默認為 `128` )。
- 元素的 `member` 長度小于服務器屬性 `server.zset_max_ziplist_value` 的值(默認為 `64` )。
否則,程序就創建一個 `REDIS_ENCODING_SKIPLIST` 編碼的有序集。
### 編碼的轉換
對于一個 `REDIS_ENCODING_ZIPLIST` 編碼的有序集,只要滿足以下任一條件,就將它轉換為 `REDIS_ENCODING_SKIPLIST` 編碼:
- `ziplist` 所保存的元素數量超過服務器屬性 `server.zset_max_ziplist_entries` 的值(默認值為 `128` )
- 新添加元素的 `member` 的長度大于服務器屬性 `server.zset_max_ziplist_value` 的值(默認值為 `64` )
### ZIPLIST 編碼的有序集
當使用 `REDIS_ENCODING_ZIPLIST` 編碼時,有序集將元素保存到 `ziplist` 數據結構里面。
其中,每個有序集元素以兩個相鄰的 `ziplist` 節點表示,第一個節點保存元素的 `member` 域,第二個元素保存元素的 `score` 域。
多個元素之間按 `score` 值從小到大排序,如果兩個元素的 `score` 相同,那么按字典序對 `member` 進行對比,決定那個元素排在前面,那個元素排在后面。
~~~
|<-- element 1 -->|<-- element 2 -->|<-- ....... -->|
+---------+---------+--------+---------+--------+---------+---------+---------+
| ZIPLIST | | | | | | | ZIPLIST |
| ENTRY | member1 | score1 | member2 | score2 | ... | ... | ENTRY |
| HEAD | | | | | | | END |
+---------+---------+--------+---------+--------+---------+---------+---------+
score1 <= score2 <= ...
~~~
雖然元素是按 `score` 域有序排序的,但對 `ziplist` 的節點指針只能線性地移動,所以在 `REDIS_ENCODING_ZIPLIST` 編碼的有序集中,查找某個給定元素的復雜度為 \(O(N)\) 。
每次執行添加/刪除/更新操作都需要執行一次查找元素的操作,因此這些函數的復雜度都不低于 \(O(N)\) ,至于這些操作的實際復雜度,取決于它們底層所執行的 `ziplist` 操作。
### SKIPLIST 編碼的有序集
當使用 `REDIS_ENCODING_SKIPLIST` 編碼時,有序集元素由 `redis.h/zset` 結構來保存:
~~~
/*
* 有序集
*/
typedef struct zset {
// 字典
dict *dict;
// 跳躍表
zskiplist *zsl;
} zset;
~~~
`zset` 同時使用字典和跳躍表兩個數據結構來保存有序集元素。
其中,元素的成員由一個 `redisObject` 結構表示,而元素的 `score` 則是一個 `double` 類型的浮點數,字典和跳躍表兩個結構通過將指針共同指向這兩個值來節約空間(不用每個元素都復制兩份)。
下圖展示了一個 `REDIS_ENCODING_SKIPLIST` 編碼的有序集:
![digraph zset { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; label = "在實際中,字典和跳躍表通過指針來共享元素的 member 和 score\n圖中對每個元素都重復顯示了一遍,只是為了展示的方便"; zset [label = "<head>zset |<dict>dict |<zskiplist> zskiplist"]; // skiplist skiplist [label ="<head>zskipNode |<3> |<2> |<1> |<score>score\n NULL |<robj>robj\n NULL", fillcolor = "#FADCAD"]; six [label = "<head>zskipNode |<3> |<2> |<1> |<score>score\n 6 |<robj>robj\n x", fillcolor = "#FADCAD"]; ten [label = "<head>zskipNode | <1> |<score>score\n 10 |<robj>robj\n y", fillcolor = "#FADCAD"]; fiften [label = "<head>zskipNode |<3> |<2> |<1> |<score>score\n 15 |<robj>robj\n z", fillcolor = "#FADCAD"]; zset:dict -> dict:head; zset:zskiplist -> skiplist:head; skiplist:3 -> six:3; skiplist:2 -> six:2; skiplist:1 -> six:1; six:1 -> ten:1; six:2 -> fiften:2; six:3 -> fiften:3; ten:1 -> fiften:1; // dict dict [label = "<head>dictht | ... |<table> table | ...", fillcolor = "#A8E270"]; bucket [label = "<head>dictEntry**\n(bucket) |<0> 0 |<1> 1 |<2> 2", fillcolor = "#95BBE3"]; entry_x [label = "<head>dictEntry |{<key>key\n x |<value>value\n 6}", fillcolor = "#F2F2F2"]; entry_y [label = "<head>dictEntry |{<key>key\n y |<value>value\n 10}", fillcolor = "#F2F2F2"]; entry_z [label = "<head>dictEntry |{<key>key\n z |<value>value\n 15}", fillcolor = "#F2F2F2"]; dict:table -> bucket:head; bucket:0 -> entry_x:head; bucket:1 -> entry_y:head; bucket:2 -> entry_z:head;}](https://box.kancloud.cn/2015-09-13_55f4effd05d06.svg)
通過使用字典結構,并將 `member` 作為鍵,`score` 作為值,有序集可以在 \(O(1)\) 復雜度內:
- 檢查給定 `member` 是否存在于有序集(被很多底層函數使用);
- 取出 `member` 對應的 `score` 值(實現 [ZSCORE](http://redis.readthedocs.org/en/latest/sorted_set/zscore.html#zscore "(in Redis 命令參考 v2.8)") 命令)。
另一方面,通過使用跳躍表,可以讓有序集支持以下兩種操作:
- 在 \(O(\log N)\) 期望時間、 \(O(N)\) 最壞時間內根據 `score` 對 `member` 進行定位(被很多底層函數使用);
- 范圍性查找和處理操作,這是(高效地)實現 [ZRANGE](http://redis.readthedocs.org/en/latest/sorted_set/zrange.html#zrange "(in Redis 命令參考 v2.8)") 、 [ZRANK](http://redis.readthedocs.org/en/latest/sorted_set/zrank.html#zrank "(in Redis 命令參考 v2.8)") 和 [ZINTERSTORE](http://redis.readthedocs.org/en/latest/sorted_set/zinterstore.html#zinterstore "(in Redis 命令參考 v2.8)") 等命令的關鍵。
通過同時使用字典和跳躍表,有序集可以高效地實現按成員查找和按順序查找兩種操作。