【Redis5源码学习】2019-04-16 跳跃表skiplist

摘要：使用跳跃表而不是平衡树的原因和各种平衡树如红黑树等的元素是有序排列的，而哈希表不是有序的。如果想要了解有关跳跃表源码更具体的分析，建议阅读学习笔记源码学习之跳跃表。

Grape
全部视频：https://segmentfault.com/a/11...

大家想象一下下面这种场景：

面试官：我们有一个有序的数组2,5,6,7,9，我们要去查7，设计一个算法。
考生：第一眼看到相信大家都会看出来是二分查找，O(logN)就完事了。
面试官：那么接下来我们把这个数组换成链表呢(2->5->6->7->9)？
考生：这简单，二叉树，同样logN。
面试官：那么请手写一下完整代码！
考生：卒

想象一下，给你一张草稿纸，一只笔，一个编辑器，你能立即实现一颗红黑树，或者AVL树出来吗？ 很难吧，这需要时间，要考虑很多细节，要参考一堆算法与数据结构之类的树，还要参考网上的代码，相当麻烦。

回去之后，小明很难过，又不想被二叉树所折磨，想要找一个方法来代替二叉树，在他的不懈努力之下，终于，找出了替代红黑树的方法，它叫做skiplist。

怎么解决的呢？
首先，表是处于一个初始状态的，没有任何一个元素，类似于下图：

那么，我们继续插入一个元素2，那么它就变成了这样。

然后我们抛硬币，结果是正面，那么我们要将2插入到L2层，如下图: 

继续抛硬币，结果是反面，那么元素2的插入操作就停止了，插入后的表结构就是上图所示。接下来，我们插入元素5，跟元素2的插入一样，现在L1层插入5，如下图： 

接下来继续抛硬币，是正面的话就上升一层，否则就终止，继续插入其他新的元素。
那么最后，我们建造成的样子就如下图所示。

这样子就构造成了skiplist。当然因为规模小，结果很可能不是一个理想的跳跃表。但是如果元素个数n的规模很大，学过概率论的同学都知道，最终的表结构肯定非常接近于理想跳跃表。
这样是不是很简单？
回归正题，我们如何查找到6呢？很简单，我们看首先和6比较，发现7大于6，我们就向后走，发现相等就找到了节点7.当然，如果我们找5的话就是和6比完之后降到L2，然后和2比，比2大比6小，继续降级，找到5。
小明同学是一个很会举一反三的人，既然都知道查找这么简单了，就看看插入吧，等把增删改查都解决了，妈妈就再也不用担心我的红黑树了。

接下来我们就看看插入，我们要插入一个4，怎么办呢？
从最高层开始找到每一层比4大的节点的前一个值，然后投硬币，随机选择层数后插入，举个例子这个值为4.那么插入之后就是下图所示。

我们发现，他会新增一层，并且会在同层级之间进行连接。然后就完成了插入操作。

删除操作：
删除操作类似于插入操作，包含如下3步：1、查找到需要删除的结点 2、删除结点 3、调整指针。

到此，Skiplist的增删改查就很明确了，但是知其然我们也得知其所以然，小明同学不抛弃不放弃，想要知道他是怎么样实现的，以及在上边过程中自己的问题。

1. 为什么要投硬币？
我们先解释一下投硬币这个流程：跳跃表节点的层数限制在了64（在redis5.0之前是32），若想超过64层得连续64次抛硬币都得到正面，这得有足够多的节点，redis限定了抛硬币正面的概率为1/4，所以到达64层的概率为(1/2)^128，一般一台64位的计算机能拥有的最大内存也无法存储这么多zskiplistNode，所以对于基本使用 64层的上限已经足够高了，再高也没必要 浪费头节点的内存。所以，投硬币是为了让数据尽量都在低的层级以达到节省内存的目的。

2. 跳跃表是什么？在哪用？
跳跃表( skiplist) 是一种有序的数据结构, 它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。跳跃表支持平均O(logN),最坏O(N)复杂度的节点查找. 大部分情况下,跳跃表的效率可以和平衡树想媲美,并且跳跃表的实现比平衡树更为简单。
Redis 使用跳跃表作为有序集合键的底层实现之一, 如果一个有序集合包含的元素数量较多,或者有序集合中元素的成员是比较长的字符串, Redis 会使用跳跃表来作为有序集合的底层实现。
那跳表这么棒在Redis中用到的地方肯定非常多吗？答案是否定的，Redis 只在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群节点中用作内部数据结构, 除此之外,跳跃表在 Redis 中没有其他用途。

3. 跳跃表是怎么实现的？
我们来看一看skiplist的源码：

      typedef struct zskiplistNode {
            sds ele;        //元素
            double score;   //分值
            struct zskiplistNode *backward;   //后退指针，后退指针用于从表尾向表头访问节点,跟可以一次跳过多个节点的前进指针不同,每个节点只有一个后退指针
            struct zskiplistLevel {
                struct zskiplistNode *forward;   //前进指针，每个层都有一个指向表尾方向的指针.用于从表头向表尾方向访问节点
                unsigned long span;   //跨度，层的跨度用于记录两个节点之间的距离. 两个节点之间的跨度越大,它们距离越远;指向 NULL 的节点的跨度为0
            } level[];   
        } zskiplistNode;
        //跳跃表的 level 数组可以包含多个元素,每个元素都包含一个指向其他节点的指针,程序可以通过这些指针加快访问速度
        //一般来说,层的数量越多,访问其他节点的速度越快
        //每次创建一个新跳跃表节点时,程序会根据幂次定律(越大的数出现的概率越小)随机生成一个介于1 和 64 之间的值作为 level 数组的大小,这个大小就是层的高度
    typedef struct zskiplist {
        struct zskiplistNode *header, *tail;    //表头和表尾指针
        unsigned long length;       //节点的数量
        int level;      //层数最大的节点的层数
    } zskiplist;
    

由此我们可以得出skiplist内存结构图如下：

抽象内存结构图如下：

另外呢？ 我们在gdb有序集合zset代码的时候，发现程序会在创建skiplist的之前会先创建一个字典dict。那么，这个dict的作用是什么呢？dict的作用呢是一个hashtable，用来映射元素与zset中分值score的关系。拥有这个映射表，我们去查找一个元素的分值时间复杂度就变成了O(1)。

4. redis使用跳跃表而不是平衡树的原因
skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。

在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。

平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。

从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。

查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。

从算法实现难度上来比较，skiplist比平衡树要简单得多。

最后，学以致用，知道skiplist是怎么回事，我们还需要知道它的老东家在怎么用它，大家可以想一下Redis中的ZADD，ZRANGE,ZRANGEBYSCORE等命令是怎么用到它的。

如果想要了解有关跳跃表源码更具体的分析，建议阅读【Redis学习笔记】2018-05-29 redis源码学习之跳跃表。