# 有序集
[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)") 等命令的关键。
通过同时使用字典和跳跃表，有序集可以高效地实现按成员查找和按顺序查找两种操作。
