葡萄全视频：https://segmentfault.com/a/11...介绍大家想象一下下面的场景：面试官：我们有一个排序好的array是2,5,6,7,9，我们要检查7并设计一个算法。考生：乍一看，相信大家都会看出是二分查找，O(logN)就结束了。面试官：那我们要不要把这个数组换成链表（2->5->6->7->9）？考生：这个很简单，二叉树，一样的logN。面试官：那请手写完整的代码！考生：想象一下，给你一张草稿纸，一支笔，一个编辑器，你能不能马上实现红黑树，或者AVL树？难，需要时间，需要考虑很多细节，一堆算法和数据结构之类的树要参考，还有网上的代码，挺麻烦的。回来后，小明很难过，不想再被二叉树折磨。他想找到一种方法来代替二叉树。在他的不懈努力下，他终于找到了一种替代红黑树的方法，叫做skiplist。skiplist的诞生是如何解决的？首先，表格处于初始状态，没有任何元素，类似下图：然后，我们继续插入一个元素2，就变成了这样。然后我们抛硬币，结果是正面，那么我们需要向L2层插入2，如下图：继续抛硬币，结果是反面，那么元素2的插入操作就停止了，并且插入后的表结构如上图所示。接下来我们插入元素5，和插入元素2一样，现在在L1层插入5，如下图：接下来继续抛硬币，如果是正数，就往上一层，否则停止，继续插入其他新元素。那么最后，我们搭建的就是如下图所示。这样就构造了一个skiplist。当然因为体积小，结果很可能不是一个理想的跳表。但是如果元素个数n很大，学过概率论的同学都知道，最终的表结构肯定非常接近理想的跳表。是不是很简单？回到主题，我们如何找到6？这很简单。让我们先将它与6进行比较。如果我们发现7大于6，我们就往回走。如果发现相等，就找节点7。当然，如果是找5，我们会先和6比较后降到L2，再和2比较，比2大，比6小，继续退化，发现5.小明是一个非常擅长从一个实例推断出其他事物的人。现在我们都知道搜索是如此简单，让我们看看插入。增删改查全部解决后，妈妈再也不用为我的红黑树操心了。skiplist的增删改查接下来我们来看插入。我们要插入一个4，怎么办？从最上面的层开始，找出每层大于4的前一个值，然后抛硬币，随机选择层数插入，比如值为4。那么插入后，就会如下图所示.我们发现他会增加一个新的层，并在相同的层之间进行连接。然后插入操作就完成了。删除操作：删除操作类似于插入操作，包括以下3个步骤：1.找到要删除的节点2.删除节点3.调整指针。至此，Skiplist的增删改查已经很清楚了，但是我们也知道为什么，小明不放弃也不放弃，想知道他是怎么实现的，以及他自己在里面的问题以上过程。四个问题skiplist1。你为什么要扔硬币？先解释一下抛硬币的过程：跳表节点的层数限制为64层（redis5.0之前是32层），如果要超过64层，必须连续64次抛硬币得到正数，这必须有足够多的Node，redis把抛硬币的概率限制在1/4，所以到达64层的概率是(1/2)^128。一般64位计算机所能拥有的最大内存不能存放那么多的zskiplistNode，所以64层的上限对于基本使用来说已经够高了，再高也没有必要浪费头节点的内存这是。因此，抛硬币是为了节省内存，让数据尽可能低。2、什么是跳表？在哪里使用它？跳表（skiplist）是一种有序的数据结构，通过在每个节点中维护多个指向其他节点的指针来达到快速访问节点的目的。跳表支持平均O(logN)和最差O(N)复杂度节点查找。在大多数情况下，跳表的效率可以和平衡树相提并论，而且跳表的实现比平衡树简单。Redis使用跳转表作为有序集合键的底层实现之一。如果一个有序集合包含大量元素，或者有序集合中元素的成员都是比较长的字符串，Redis会使用跳表作为有效key。有序集合的底层实现。跳表这么好用，Redis里面很多地方都要用到吗？答案是否定的，Redis只是在两个地方使用了跳表，一个是实现有序集合键，另一个是作为集群节点中的内部数据结构。除此之外，跳转表在Redis中没有其他用处。3、跳表是如何实现的？我们看一下skiplist的源码：typedefstructzskiplistNode{sdsele;//元素双倍得分；//得分structzskiplistNode*backward;//后向指针，用于访问链表尾部到链表头的节点，后面跟着不同的前向指针，可以一次跳过多个节点，每个节点只有一个后向指针structzskiplistLevel{structzskiplistNode*向前;//前向指针，每一层都有一个指向表尾的指针。用于从表头开始访问到表尾的节点unsignedlongspan；//span，层的span用来记录两个节点之间的距离。两个节点之间的跨度越大，它们之间的距离就越远；指向NULL的节点跨度为0}level[];}zskiplist节点；//跳表的层级数组可以包含多个元素，每个元素包含一个指向其他节点的指针，程序可以利用这些指针来加快访问速度//一般来说层级的数量越多速度越快theaccesstoothernodes//每创建一个新的跳表节点，程序会根据幂律随机生成一个1到64之间的节点（数字越大，出现概率越小）的值value作为level数组的大小，也就是层的高度typedefstructzskiplist{structzskiplistNode*header,*tail;//头尾指针unsignedlonglength;//节点数intlevel;//numberoflayers最大节点的层数}zskiplist;由此我们可以画出skiplist内存结构图如下：抽象的内存结构图如下：还有什么？当我们按顺序收集gdb中的zset代码时，我们发现程序会在之前创建skiplist首先会创建一个字典dict。那么，这个字典的作用是什么？dict的作用是一个hashtable，用于映射元素与zset中score的关系。有了这个映射表，我们找到一个元素的分数的时间复杂度就变成了O(1)。4、redis使用skiplist而不是平衡树的原因skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而hash表是无序的。因此，哈希表只能进行单键查找，不适合范围查找。所谓范围搜索，就是找到大小在两个指定值之间的所有节点。在进行范围查找时，平衡树比跳表操作更复杂。在平衡树上，我们找到指定范围内的小值后，需要按照中序遍历的顺序继续寻找其他不超过大值的节点。这里的中序遍历如果不对平衡树做一些修改是不容易实现的。在skiplist上执行范围搜索非常简单。找到小值后只需要遍历第一层链表几步即可。平衡树的插入和删除操作可能会引起子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，简单快速。在内存使用方面，skiplist比balancedtree更灵活。一般来说，平衡树的每个节点包含2个指针（分别指向左右子树），skiplist的每个节点包含的指针个数平均为1/(1-p)，具体取决于大小参数p。如果像Redis中的实现一样取p=1/4，那么每个节点平均包含1.33个指针，比平衡树更有优势。查找单个key、skiplist和平衡树的时间复杂度都是O(logn)，大致相同；而哈希表保持较低的哈希值碰撞概率，搜索时间复杂度接近O(1)，性能更高。因此，我们平时使用的各种Map或者字典结构，大多都是基于哈希表来实现的。相对于算法实现的难度，skiplist要比平衡树简单的多。在最后一章的最后，我们需要学以致用，知道skiplist是什么。我们还需要知道它的老主人是如何使用它的。大家可以想想Redis中的ZADD、ZRANGE、ZRANGEBYSCORE等命令是怎么使用的。如果想了解跳表源码更具体的分析，推荐阅读【Redis学习笔记】2018-05-29redis源码学习跳表。
