华为架构师整理Redis数据结构的大厂最佳实践( 六 ) _Redis

用户在排行榜里的排名：
127.0.0.1:6379> zrank board JavaEdge(integer) 0127.0.0.1:6379> zadd board 85 zhangsan(integer) 1127.0.0.1:6379> zadd board 72 wangwu(integer) 1127.0.0.1:6379> zadd board 96 lisi(integer) 1127.0.0.1:6379> zadd board 62 zhaoliu(integer) 1# 获取排名前3的用户127.0.0.1:6379> zrevrange board 0 31) "lisi"2) "zhangsan"3) "wangwu"4) "zhaoliu"127.0.0.1:6379> zrank board zhaoliu(integer) 1类似于Map的key-value对，但有序

key ：key-value对中的键，在一个Sorted-Set中不重复
value ：浮点数，称为 score
有序：内部按照score 从小到大的顺序排列

基本操作由于Sorted-Set 本身包含排序信息，在普通Set 的基础上，Sorted-Set 新增了一系列和排序相关的操作：

Sorted-Set的基本操作

内部数据结构Sorted-Set类型的valueObject 内部结构有两种：

ziplist
实现方式和Map类似，由于Sorted-Set包含了Score的排序信息，ziplist内部的key-value元素对的排序方式也是按照Score递增排序的，意味着每次插入数据都要移动之后的数据，因此ziplist适于元素个数不多，元素内容不大的场景。
skiplist+hashtable
更通用的场景，Sorted-Set使用sliplist来实现。

8.2.1 zskiplist和通用的跳表不同的是，Redis为每个level 对象增加了span 字段，表示该level 指向的forward节点和当前节点的距离，使得getByRank类的操作效率提升

数据结构
结构示意图

每次向skiplist 中新增或者删除一个节点时，需要同时修改图标中红色的箭头，修改其forward和span的值。
需要修改的箭头和对skip进行查找操作遍历并废弃过的路径是吻合的。span修改仅是+1或-1 。
zskiplist 的查找平均时间复杂度 O(Log(N))，因此add / remove的复杂度也是O(Log(N)) 。因此Redis中新增的span 提升了获取rank（排序）操作的性能，仅需对遍历路径相加即可（矢量相加）。
还有一点需要注意的是，每个skiplist的节点level 大小都是随机生成的（1-32之间）。

zskiplistNode源码

8.2.2 hashtablezskiplist 是zset 实现顺序相关操作比较高效的数据结构，但是对于简单的zscore操作效率并不高。Redis在实现时，同时使用了Hashtable和skiplist，代码结构如下：

文章插图

Hash表的存在使得Sorted-Set中的Map相关操作复杂度由O(N)变为O(1) 。
Redis有序集合类型与Redis的集合类型类似，是非重复的String元素的集合。不同之处在于，有序集合中的每个成员都关联一个Score，Score是在排序时候使用的，按照Score的值从小到大进行排序。集合中每个元素是唯一的，但Score有可能重复。
使用有序集合可以很高效的进行，添加，移除，更新元素的操作（时间消耗与元素个数的对数成比例）。由于元素在集合中的位置是有序的，使用get ranges by score或者by rank（位置）来顺序获取或者随机读取效率都很高。（本句不确定，未完全理解原文意思，是根据自己对Redis的浅显理解进行的翻译）访问有序集合中间部分的元素也非常快，所以可以把有序集合当做一个不允许重复元素的智能列表，你可以快速访问需要的一切：获取有序元素，快速存在测试，快速访问中间的元素等等。
简短来说，使用有序集合可以实现很多高性能的工作，这一点在其他数据库是很难实现的。
应用