Redis - zset底层数据结构实现

zset为有序的，自动去重的集合数据类型，zset数据结构底层实现为字典(dict) + 跳表(skiplist)，当数据比较少时，用ziplist编码结构存储，element和score各占一个entry.

ele1 - score1 - ele2 - score2 ...

redis.conf有以下两个参数控制

zset-max-ziplist-entries 128 // 元素个数超过128，将用skiplist编码

zset-max-ziplist-value 64 // 单个元素大小超过64byte，将用skiplist编码

加入的元素个数较少，且key的长度小于64byte时，使用ziplist有序存储元素。

往zset添加一个长度为65byte的key，此时底层选用skiplist存储元素。

利用dict可以以O(1)时间复杂度判断某个key'是否存在，以及取出key的分值。

skiplist是一个有多个索引层，一个数据层的数据结构，索引层和数据层都是有序的双向列表。

每个索引层的元素，都有两个指针字段，分别指向当前索引层下一个元素，以及下一索引层的本元素。

索引层1： 23 ----------- 52 ----------- 65 --------------- 76 ---------- null

索引层2:23 ----43---- 52 ----59---- 65 -----70------- 76 ----84---- null

数据层： 23 -32-43-47- 52 -55-59-61- 65 --67-70-74- 76 -79-84--86-null

N: 节点数量

index: 1--- N/2^1

index: 2 --- N/2^2

index: 3 --- N/2^3

index: k --- N/2^k

顶层只有两个元素： 2^k = N / 2 --- >k = log2(N-1)

时间复杂度：每一个索引层最多查找两次，层数为 log2(N-1) --->2 * log2(N-1) = log(N)，与二分查找时间复杂度一样。

zset相关的问题，算是面试中的高频问题了。那么zset到底是什么？底层的实现原理是什么？相关的使用场景有哪些？

1. zset是什么？

在redis官网（ https://redis.io/ ）上，我们可以看到set, sorted set。其实zset就是sorted set。为了避免sorted set简写sset导致命令冲突，所以改为zset。同理例如class-->clazz

        sorted set从字面意思上，很容易就可以理解，是个有序且不可重复的数据集合。类似set和hash的混合体，但是相比于set，zset内部由score进行排序.

2. zset中的score排序规则 

升序排列，分值越大越靠后

分值相同，则按照value的字典顺序排序      

3. zset的用法

zset的命令可在这里（ http://www.redis.cn/commands.html#sorted_set ）看到，有兴趣的同学可以直接去看。

ZADD key score1 value1 score2 value2........

即表示增加是的score和value 组，可同时增加多个

 4. zset实现

在redis.conf中，有如下两个参数：

zset-max-ziplist-entries 128

zset-max-ziplist-value 64

这两个条件均不满足，使用ziplist压缩表来实现sorted set

满足这两个条件之一，sorted set的内部实现会由ziplist转换为zset

zset-max-ziplist-entries 128，即sorted set中的元素对超过128时（存储的是score和value的元素对，所以数据项是256），内部实现会由ziplist转换为zset。

zset-max-ziplist-value 64,即任意一个value的长度超过了64字节，内部实现会由ziplist转换为zset.

zset由dict、skiplist实现。

5. ziplist，即压缩列表

压缩列表是由连续性内存组成的顺序性数据结构，一个压缩列表可以包含任意多的entry,每个entry可以保存一个字节数组或者一个整数。

压缩列表在表头有三个字段：zlbytes,zltail,zllen分别表示列表长度（整个列表占用的字节数），列表尾的偏移量（尾节点距离起始地址的字节数）和列表中entry的个数。

列表表尾还有一个zlend，表示列表结束了。

6.skiplist

由上图压缩列表可知，如果我们查找第一个元素或者最后一个元素，直接通过表头三个字段的长度可定位。复杂度是O(1)，而如果查找其他元素，只能顺序查找，复杂度是O(n)。 为了解决这个问题，可以使用跳表。

在新增节点之前，也会先经过查询，确定插入位置，再完成插入 *** 作，同时也实现了Sorted Set的排序。

跳表中新增加节点不会影响其他节点的索引位置。因此插入 *** 作只需要修改插入节点前后的指针，不需要修改所有节点，降低了插入的复杂度，所以跳表在插入性能上明显优于平衡树。

 7. zset的使用场景

需要排序的场景，比如top10的热点文章，或者排行榜

消息的延迟发送，用score存储发送时间戳，定时任务扫描sorted set，判断时间进行发送。

---