Redis数据类型——zset（sorted set）

简介

• 新的存储需求：数据排序有利于数据的有效展示，需要提供一种可以根据自身特征进行排序的方式
• 需要的存储结构：新的存储模型，可以保存可排序的数据
• sorted_set类型：在set的存储结构基础上添加可排序字段
  

数据结构

它类似于 Java 的 SortedSet 和 HashMap 的结合体，一方面它是一个 set，保证了内部 value 的唯一性，另一方面它可以给每个 value 赋予一个 score，代表这个 value 的排序权重。它的内部实现用的是一种叫着「跳跃列表(skiplist）」的数据结构。

跳跃列表(skiplist）

上图就是跳跃列表的示意图，图中只画了四层，Redis 的跳跃表共有 64 层，意味着最多可以容纳 2^64 次方个元素。每一个 kv 块对应的结构如下面的代码中的 zslnode 结构，kv header 也是这个结构，只不过 value 字段是 null 值——无效的，score 是 Double.MIN_VALUE，用来垫底的。kv 之间使用指针串起来形成了双向链表结构，它们是有序排列的，从小到大。不同的 kv 层高可能不一样，层数越高的 kv 越少。同一层的 kv 。会使用指针串起来。每一个层元素的遍历都是从 kv header 出发。

struct zsl {   
	zslnode* header;  // 跳跃列表头指针   
	int maxLevel;  // 跳跃列表当前的最高层   
	map<string, zslnode*> ht;  // hash 结构的所有键值对 
} 

struct zslnode {   
	string value;   
	double score;   
	zslnode*[] forwards;  // 多层连接指针   
	zslnode* backward;  // 回溯指针
 }

查找

如图所示，我们要定位到那个紫色的 kv，需要从 header 的最高层开始遍历找到第一个节点 (最后一个比「我」小的元素)，然后从这个节点开始降一层再遍历找到第二个节点 (最后一个比「我」小的元素)，然后一直降到最底层进行遍历就找到了期望的节点 (最底层的最后一个比我「小」的元素)。 我们将中间经过的一系列节点称之为「搜索路径」，它是从最高层一直到最底层的每一层最后一个比「我」小的元素节点列表。
更详细的跳跃表的查找方法见大佬文章：跳跃表以及跳跃表在redis中的实现

如何排名

那这个 rank 是如何算出来的？如果仅仅使用上面的结构，rank 是不能算出来的。Redis 在 skiplist 的 forward 指针上进行了优化，给每一个 forward 指针都增加了 span 属性，span 是「跨度」的意思，表示从前一个节点沿着当前层的 forward 指针跳到当前这个节点中间会跳过多少个节点。这样当我们要计算一个元素的排名时，只需要将「搜索路径」上的经过的所有节点的跨度 span 值进行叠加就可以算出元素的最终 rank 值。

struct zslforward {   
	zslnode* item;   
	long span;  // 跨度 
} 

struct zsl {   
	String value;   
	double score;   
	zslforward*[] forwards;  // 多层连接指针   
	zslnode* backward;  // 回溯指针 
}

常用命令

增：zadd key score member [score1 member1]
删：zrem key member [member1]
获取全部（正序）：zrange key start stop [withscores]
获取全部（倒序）：zrevrange key start stop [withscores]
按条件查（正序）：zrangebyscore key min max [withscore limit]
按条件查（倒序）：zrevrangebyscore key max min [withscore limit]
按条件删除（索引）：zremrangebyrank key start stop
按条件删除（积分）：zremrangebyscore key min max
获取集合总量：zcard key | zcount key min max
存储集合交集： zinterstore destination numkeys key key1
存储集合并集：zunionstore destination numkeys key key1
获取索引（正序）：zrank key member
获取索引（倒序）：zrevrank key member
score值获取：zscore key member
score值修改：zincrby key num member

注意事项

• score保存的数据存储空间是64位，如果是整数范围是-9007199254740992~9007199254740992 （Long.MAX_VALUE）
• score保存的数据也可以是一个双精度的double值，基于双精度浮点数的特征，可能会丢失精度，使用时 候要慎重
• sorted_set 底层存储还是基于set结构的，因此数据不能重复，如果重复添加相同的数据，score值将被反 复覆盖，保留最后一次修改的结果

使用场景

• 天然的排行榜
• 由权重的任务队列的处理