OrderedCollectionObject.md

REDIS5 有序集合对象

有序集合对象的构成

• 有序集合的编码可以是ziplist或者skiplist
• ziplist编码的压缩列表对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表点来保存，第一个节点保存元素的成员(member), 而第二个元素则保存元素的分值(score)
  • 压缩列表的集合元素按分值从小到大进行排序，分值较小的元素被放置在靠近表头的方向
  • 而分值较大的元素则被放置在靠近表尾的方向
• skiplist 编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表

  typedef struct zset {
    zskiplist *zsl;
    dict *dict;
  } zset;
  

  • zset结构中的zsl跳跃表分值从小到大保存来所有元素，每个跳跃表都保存一个集合元素
    • 跳跃表节点的object属性保存了元素的成员，而跳跃表节点的score属性则保存了元素的分值
    • 通过这个跳跃表，程序可以对有序集合进行范围操作，比如ZRANK，ZRANGE等命令
  • zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值都保存了一个集合元素
    • 字典的键保存了元素的成员，而字典的值保存了元素的分值
    • 通过这个字典，程序可以用O(1)复杂度查找给定成员的分值, ZSCORE命令就是根据这特性实现的
• 为什么有序集合需要同时使用跳跃表和字典来实现？
  • 如果只使用字典来实现有序集合，虽然以O(1)复杂度查找成员分值
  • 但是，字典是以无序的方式保存集合元素，所以每次执行范围操作 - ZRANK, ZRANGE等命令时
  • 程序都需要对字典保存的所有元素操作进行排序，完成这种排序需要至少O(NlogN)时间复杂度和额外O(N)内存空间
  • 如果，只使用跳跃表来实现有序集合，那么跳跃表执行范围型操作的优点被保留，但是因为没有字典，根据用户查询分值这一操作的复杂度将从O(1)上升到(logN)

编码的转换

• 当有序集合对象可以同时满足以下两个条件时候，对象使用ziplist编码
  • 有序集合保存的元素数量小于128个
  • 有序集合保存的所有元素成员的长度都小于64字节
• 不能满足以上两个条件的有序集合对象将使用skiplist编码

有序集合命令的实现方法

命令	ziplist编码的实现方法	zset编码实现方式
ZADD	调用ziplistInsert函数，将成员和分值为两个节点插入到压缩列表	先调用zslInsert函数，将新元素添加到跳跃表，然后调用dictAdd函数，将新元素关联到字典
ZCARD	调用ziplistLen函数，获得压缩列表包含节点数量，将这个数量除以2得到集合元素的数值	访问跳跃表数据结构的length属性，直接返回集合元素的数量
ZCOUNT	遍历压缩列表，统计分值在给定范围内的节点的数量	遍历跳跃表，统计分值在给定范围的节点数量
ZRANGE	从表头向表尾遍历压缩列表，返回索引范围内的所有元素	从表头向表尾遍历跳跃表，返回给定索引范围内的所有元素
ZREVRANGE	从表尾向表头遍历压缩列表，返回给定索引范围内的所有元素	从表尾向表头遍历跳跃表，返回给定索引范围内的所有元素
ZRANK	从表头向表尾遍历压缩列表，查找给定的成员，沿途记录经过节点的数量，当找到给定成员之后，沿途节点的数量就是该成员所对应的元素的排名	从表尾向表头遍历跳跃表，查找给定的成员，沿途记录经过节点的数量，当找到给定成员之后，沿途节点的数量就是该成员所对应的元素的排名
ZREVRANK	从表尾向表头遍历压缩列表, 查找给定的成员，沿途记录经过节点的数量，当找到给定成员之后，沿途节点的数量就是该成员所对应的元素的排名	表尾向表头遍历跳跃表,查找给定的成员，沿途记录经过节点的数量，当找到给定成员之后，沿途节点的数量就是该成员所对应的元素的排名
ZREM	遍历压缩列表，删除所有包含给定成员的节点，以及被删除成员节点旁边的分值节点	遍历跳跃表，删除所有包含了给定成员的跳跃表节点，并在字典中删除元素的成员和分值函数
ZSCORE	遍历压缩列表，查找包含了给定成员的节点，然后取出成员节点旁边的分值节点保存的元素分值	直接从字典中取出给定成员的分值