• 欢迎来到Compiler网站,如果对网站内容感兴趣或者帮助到你,请为文章点赞,谢谢!

有序集合对象

redis 奔跑的蜗牛 6个月前 (03-28) 117次浏览 已收录 0个评论

有序集合对象

编码

有序集合的编码可以是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 遍历压缩列表, 查找包含了给定成员的节点, 然后取出成员节点旁边的分值节点保存的元素分值 直接从字典中取出给定成员的分值

Compiler编程笔记 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:有序集合对象
喜欢 (1)
[阳光路上]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址