redis 中的跳表与有序集合--redis 有序集合的实现
看了很多跳表的文章包括《redis设计与实现》，都没能很好地了解跳表。
感谢https://www.jianshu.com/p/61f8cad04177 此文。
有序集合的实现
有序集合 的实现采用了两种方式：
当有序集合对象同时满足以下两个条件时，对象使用 ziplist 编码：
1、保存的元素数量小于128；
2、保存的所有元素长度都小于64字节。
否则使用跳表（skiplist）
1. 压缩列表 ziplist
首先需要明确,压缩列表的产生是Redis为了节约内存开发的,是一个由一系列特殊编码的连续内存块组成的顺序性数据结构。一个压缩列表可以包含任意数量个节点,每个节点可以保存自己数组或者一个整数值。如下图所示
压缩列表的结构.png
zlbytes记录整个压缩列表占用的内存字节数,在对压缩列表进行内存重分配或计算zlend的位置时使用。zltail记录压缩列表尾节点距离压缩列表的起始地址有多少字节,通过这个偏移量,可以直接确定尾节点的位置。zllen记录压缩列表包含的节点数量,entryX表示各种节点,数量和长度不一定。zlend用于标记压缩列表的末端。
如图,如果有一个指针p指向该压缩列表,则尾巴节点的长度就是指针加上偏移量179(十六进制0xb3=16*11+3=179),列表的长度zllen为5,表示压缩列表包含5个节点。zlbytes为0xd2表示压缩列表的总长为210字节。
压缩列表的计算.png
由上可知,每个压缩列表的节点可以保存一个字节数组或者一个整数值,那么每个节点肯定也有自己的结构。
1.2 压缩列表的节点
如图所示,每个压缩列表的节点都是由previous_entry_length、encoding、content组成的。下面分别来说一说这三个字段的含义。
节点的字段.png
1.2.1 previous_entry_length
previous_entry_length以自己为单位,记录的是压缩列表中前一个节点的长度,previous_entry_length自身的空间长度可以是1字节或者5字节。如果前一个字节的长度小于254自己,就是1字节(前一个节点的长度就保存在这里面,这两个值一个是本节点里这个字段本身的空间大小,存储的是前一个节点的空间大小,不要弄混了哈)。如果前一个大于254那么这个字段的空间长度就为5字节,存储的值为大于254的那个值(就是前一个节点的长度)。其中这5个字节,第一个字节会被设置为0xFF也就是254,之后的四个字节用来保存前一个节点的长度。因为前一个节点的长度被previous_entry_length属性记录了,所以程序可以通过指针的运算根据当前节点的起始地址来计算出前一个节点的起始地址。而压缩列表的从表尾向表头的遍历操作就是通过这个原理实现的,只要我们拥有了一个指向某个节点的起始地址指针,通过这个指针和这个字段,我们可以往回遍历出所有的节点，最终到达表头。如下:
压缩列表的后序遍历.png
1.2.2 encoding
节点encoding属性记录了节点的content属性所保存的数据类型及长度。可以为一字节、两字节或者五字节长,值的最高位为00、01或者10的是字节数组编码，这种编码表示节点的content属性保存着字节数组,数组的长度由编码除去最高2位之后的其他位记录。也就是说高2位其实代表的是类型是字节数组还是整数编码。值的最高位以11开头的是整数编码：这种编码表示节点的content属性保存着整数值。整数值的类型和长度由编码除去最高2位之后的其他位的记录。
1.2.3 content
节点的content属性负责保存节点的值,节点值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定。
1.3 连锁更新
之前说过,每个节点的previous_entry_length都记录了前一个节点的长度,如果长度小于254那么previous_entry_length需要用1字节来保存这个长度值。现在假设这种情况:压缩列表有多个连续的长度介于250-253之间的节点e1-eN。因为每个节点的长度都小于254字节，所以这些节点的previous_entry_length属性都是1字节长度。此时如果将一个长度大于254的新节点设置为压缩列表的头节点，那么这个新节点成为头节点，也就是e1节点的前置节点。此时将e1的previous_entry_length扩展为5字节长度,此时e1又超过了254，于是e2的previous_entry_length也超过了254··· .此时这些节点就会连锁式的更新，并重新分配空间。除了新增加的节点会引发连锁更新之外，删除也会。假设中间有一个小于250的删除了，也会连锁更新。同上面所说的类似。因为连锁更新在最坏的情况下需要对压缩列表执行N次空间重分配操作，而每次空间重分配的最坏复杂度为O(N),所以连锁更新的最坏复杂度为`O(N^2)。虽然这很耗费时间，但是实际情况下这种发生的概率非常低的。对很少一部分节点进行连锁更新绝对不会影响性能的。
2.跳跃表
什么是跳跃表*
跳跃表是一种有序的数据结构，它通过在每个节点中维持多个指向其他的几点指针，从而达到快速访问队尾目的。跳跃表的效率可以和平衡树想媲美了，最关键是它的实现相对于平衡树来说，代码的实现上简单很多。
跳跃表用在哪
说真的，跳跃表在 Redis 中使用不是特别广泛，只用在了两个地方。一是实现有序集合键，二是集群节点中用作内部数据结构。
跳跃表原理
我们先来看一下一张完整的跳跃表的图。（图片来自《Redis 设计与实现》）
完整跳跃表
跳跃表的 level 是如何定义的？
跳跃表 level 层级完全是随机的。一般来说，层级越多，访问节点的速度越快。
跳跃表的插入
首先我们需要插入几个数据。链表开始时是空的。
链表开始
插入 level = 3，key = 1
当我们插入 level = 3，key = 1 时，结果如下：
level = 3，key = 1
插入 level = 1，key = 2
当继续插入 level = 1，key = 2 时，结果如下
level = 1，key = 2
插入 level = 2，key = 3
当继续插入 level = 2，key = 3 时，结果如下
level = 2，key = 3
插入 level = 3，key = 5
当继续插入 level = 3，key = 5 时，结果如下
level = 3，key = 5
插入 level = 1，key = 66
当继续插入 level = 1，key = 66 时，结果如下
level = 1，key = 66
插入 level = 2，key = 100
当继续插入 level = 2，key = 100 时，结果如下
level = 2，key = 100
上述便是跳跃表插入原理，关键点就是层级–使用抛硬币的方式，感觉还真是挺随机的。每个层级最末端节点指向都是为 null，表示该层级到达末尾，可以往下一级跳。
跳跃表的查询
现在我们要找键为 66 的节点的值。那跳跃表是如何进行查询的呢？
跳跃表的查询是从顶层往下找，那么会先从第顶层开始找，方式就是循环比较，如过顶层节点的下一个节点为空说明到达末尾，会跳到第二层，继续遍历，直到找到对应节点。
如下图所示红色框内，我们带着键 66 和 1 比较，发现 66 大于 1。继续找顶层的下一个节点，发现 66 也是大于五的，继续遍历。由于下一节点为空，则会跳到 level 2。
顶层遍历
上层没有找到 66，这时跳到 level 2 进行遍历，但是这里有一个点需要注意，遍历链表不是又重新遍历。而是从 5 这个节点继续往下找下一个节点。如下，我们遍历了 level 3 后，记录下当前处在 5 这个节点，那接下来遍历是 5 往后走，发现 100 大于目标 66，所以还是继续下沉。
第二层遍历
当到 level 1 时，发现 5 的下一个节点恰恰好是 66 ，就将结果直接返回。
遍历第一层
跳跃表删除
跳跃表的删除和查找类似，都是一级一级找到相对应的节点，然后将 next 对象指向下下个节点，完全和链表类似。
现在我们来删除 66 这个节点，查找 66 节点和上述类似。
找到 66 节点
接下来是断掉 5 节点 next 的 66 节点，然后将它指向 100 节点。
指向 100 节点
如上就是跳跃表的删除操作了，和我们平时接触的链表是一致的。当然，跳跃表的修改，也是和删除查找类似，只不过是将值修改罢了，就不继续介绍了。