编码
有序集合的编码可以是ziplist或者skiplist
ziplist
ziplist编码的压缩列表对象使用压缩列表作为底层实现, 每个集合元素使用两个紧挨在一起的压缩列表节点来保存, 第一个节点保存元素的成员(member), 第二个元素保存元素的分值(score)
压缩列表内的集合元素按分值从小到大进行排序, 分值较小的元素被放置在靠近表头的方向, 而分值较大的元素则被放置在靠近表尾的方向
有序集合压缩列表实现方式
skiplist编码的有集合对象使用zset结构作为底层实现, 一个zset结构同时包含一个字典和一个跳跃表
typedef struct zset {
zskiplist *zsl;
dict *dict;
} zset;
-
zsl跳跃表按照分值从小到大保存了所有集合元素, 每个跳跃表节点都保存了一个集合元素
-
object属性保存了元素的成员 -
score属性保存了元素的分值 -
通过这个跳跃表可以对有序集合进行范围型操作, 例如
ZRANK,ZRANGE
-
-
dict创建了一个成员到分值的映射, 字典中的每个键值对都保存了一个集合元素-
字典的键保存了元素的成员
-
字典的值保存了元素的分值
-
通过这个dict可以以
O(1)复杂度查找给定成员的分值.
-
共享成员
虽然zset结构同时使用跳跃表和字典来保存有序集合元素, 但这两种数据结构都会通过指针来共享相同的成员和分值. 所以跳跃表和字典来保存集合元素不会产生任何重复成员或者分值, 也不会因此而浪费额外的内存。
为什么使用跳跃表和字典来实现
-
如果单纯的使用
hashtable, 那么hashtable查询数据O(1)的特性被保留, 但是如果对hashtable进行范围查找时,-
需要重新对数据按照分值进行排序,完成排序至少需要
O(NlogN)时间复杂度 -
另外需要存储最终的排序结果, 需要额外的
O(N)内存空间
-
-
如果单纯使用
skiplist, 那么跳跃表执行范围性操作有点被保留, 但是对元素的查询操作则由O(1)上升为O(logN)
基于以上原因, Redis选择了同时使用字典和跳跃表两种数据结构来实现有序集合.
编码的转换
当有序集合对象可以同时满足以下两个条件时, 对象使用ziplist编码:
-
有序集合保存的元素数量小于
128个 -
有序集合保存的所有元素成员的长度都小于64字节.
不能满足以上两个条件的有序集合对象将使用skiplist编码
修改编码转换条件
-
zset-max-ziplist-entries: 压缩列表所能存储的最大节点数量 -
zset-max-ziplist-value: 压缩节点能存储的值最大的长度
有序集合命令
| 命令 | ziplist编码的实现方法 | zset编码的实现方法 |
|---|---|---|
| ZADD | 调用ziplistInsert函数, 将成员和分值作为两个节点分别插入到压缩列表中 |
先调用zslInsert函数, 将新元素加到跳跃表, 然后调用dictAdd函数, 将新元素关联到字典 |
| ZCARD | 调用ziplistLen函数, 获得压缩列表包含节点的数量, 将这个数量除以2得出集合元素的数量 |
访问跳跃表数据结构的length属性, 直接返回结合元素的数量 |
| ZCOUNT | 遍历压缩列表, 统计分值在给定范围内的节点的数量 | 遍历跳跃表, 统计分值在给定范围内的节点的数量 |
| ZRANGE | 从表头向表尾遍历压缩列表, 返回给定索引范围内的所有元素 | 从表头向表尾遍历跳跃表, 返回给定索引范围内的所有元素 |
| ZREVRANGE | 从表尾向表头遍历压缩列表, 返回给定索引范围内的所有元素 | 从表尾向表头遍历跳跃表, 返回给定索引范围内的所有元素 |
| ZRANK | 从表头向表尾遍历压缩列表, 查找给定的成员, 沿途记录经过节点的数量, 当找到给定成员之后, 沿途节点的熟练就是该成员所对应元素的排名 | 从表头向表尾遍历跳跃表, 查找给定的成员, 沿途记录经过节点的数量, 当找到给定成员之后, 沿途节点的数量就是该成员所对应元素的排名 |
| ZREVRANK | 从表尾向表头遍历压缩列表, 查找给定的成员, 沿途记录经过节点的数量, 当找到给定成员之后, 沿途节点的数量就是该成员所对应元素的排名 | 从表尾向表头遍历跳跃表, 查找给定的成员, 沿途记录经过节点的数量, 当找到给定成员之后, 途径节点的数量就是该成员所对应元素的排名 |
| ZREM | 遍历压缩列表, 删除所有包含给定成员的节点, 以及被删除成员节点叛变的分值节点 | 遍历跳跃表, 删除所有包含了给定成员的跳跃表节点. 并在字典中解除被删除元素的成员和分值的关联 |
| ZSCORE | 遍历压缩列表, 查找包含了给定成员的节点, 然后取出成员节点旁边的分值节点保存的元素分值 |
