redis中zset的底层实现原理
zset是什么
一种有序的集合sorted set,使用一个额外的参数score为成员排序,内部使用hashmap和跳跃表实现存储和有序,HaspMap存放成员到score的映射，而跳跃表存放所有的成员,使用跳表实现比较高的查询效率,常用命令zadd,zrange,zrem,zcard等待，使用场景用分数进行成员的从小到大的排序
zset底层实现原理
他使用两种编码是新ziplist和skiplist，根据不同情况使用不同的编码
1.元素个数小于128，同时所有member都小于64字节，使用ziplist
2.否则使用skiplist编码
zset-max-ziplist-entries 128
zset-max-ziplist-value 64ziplist结构如下
可以看出ziplist是当数据小的时候，由一段连续的内存组成,最大的优点就是节省内存，但这种结构不善于修改
skiplist
skiplist编码是有一个zset的数据结构,这个结构有两部分组成，字典dict和跳跃表,跳跃表按 score 从小到大保存所有集合元素，查找时间复杂度为平均 O(logN)，最坏 O(N) 。字典则保存着从 member 到 score 的映射，这样就可以用 O(1)的复杂度来查找 member 对应的 score 值。虽然同时使用两种结构，但它们会通过指针来共享相同元素的 member 和 score，因此不会浪费额外的内存
跳跃表是是指除了第一层以外,会建立多个稀疏的链表,这些链表会跳过部分节点，这使得我们查找数据的时候，从最高层查找数据，一层层向下查找，之后最后一层精确找到对应的数据,让我们的查找速度提高很多，如下图，查找一个23的数据
- 先从第4层找到,和7进行比较,大于7,第4层7之后没有了数据
- 然后向下一层,从第3层的7节点向后找,比较37,小于37，继续向下找
- 从第2层找,比较再从7节点往后找,比较19,大于19,继续向后找,小于37,继续向下一层找
- 到第2层,从19节点开始找,比较22,大于22,向后找,比较26,小于26,则发现没有目标节点
而我们的redis中的skipList其实和上面介绍的跳表还是有一定区别,redis的skiplist是不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。比如,一个节点随机出的层数是3，那么就把它链入到第1层到第3层这三层链表中.
并且实际应用中的skiplist每个节点应该包含key和value两部分。前面的描述中我们没有具体区分key和value，但实际上列表中是按照key(score)进行排序的，查找过程也是根据key在比较
总之,sorted set是由zipList和dict,skipList基础上构建起来的,
- 当数据较少时，sorted set是由一个ziplist来实现的。
- 当数据多的时候，sorted set是由一个叫zset的数据结构来实现的，这个zset包含一个dict + 一个skiplist。dict用来查询数据到分数(score)的对应关系，而skiplist用来根据分数查询数据（可能是范围查找)