开篇问题
我们前面讲15-二分查找（上）：如何用最省内存的方式实现快速查找功能？，二分查找依赖于数组的随机访问，所以只能用数组来实现。但是，如果数据存储在链表里，就真的没法用二分查找算法了嘛？
实际上，我们只需要把链表稍微改一下，就可以支持类似“二分”的查找算法了。我们把这种数据结构叫做 跳表。
虽然你可能会对这个数据结构有点陌生，但是它确实是一种各个方面性能都比较优秀的 动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树(red-black tree)。
Redis中的有序集合(Sorted Set)就是用跳表来实现的。如果你有一定的基础，应该知道红黑树也可以实现快速的插入、删除和查找操作。那Redis为什么会选择用跳表来实现有序集合呢？为什么不用红黑树呢？
跳表的理解
对于一个单链表来说，即便链表存储的数据是有序的，我们如果想要找到某个数据，所用的时间复杂度也是O(n)。
那我们如何更高效的查找呢？像下面这样，我们建立一级“索引”。每两个结点提取一个结点到上一级(我们把原始链表的上一级叫做第一级索引)。我们把抽取出来的这一层叫做 索引或 索引层。（图中的down表示down指针，指向下一级结点。）
简单的解释一下，我们如果要查找某个结点，比如16。我们可以先在索引层遍历，当遍历到13时，发现下一个是17，比16大，我们就通过索引层结点的down指针下降到原始链表这一层，继续遍历直到找到16。我们可以算算，本来要遍历10个结点，现在只遍历了7个结点。
我们试想一下，如果数据量比较大的话，当我们建立了多层索引时，需要遍历的次数就会降低的很明显。我们来看看：
看到这里我们大家就会知道了，其实跳表就是在链表上加了多级索引和指针帮助我们提高搜索效率。
跳表的查询时间复杂度怎么计算？
我们看到了，跳表中的索引能帮助我们提高查询效率，那它的时间复杂度应该怎么来计算呢？有这么多级的索引，那我们不是只要根据原始链表的结点数n，把索引的总层数和每层会遍历的次数都算出，然后相乘就可以得出总的时间复杂度了嘛？emmm，没毛病。
按照我们刚才讲的，我们每隔了两个结点建立一个上级索引。当原始链表有n个结点，那第一级索引节点个数约为n/2,第二级索引的个数大约就是n/4…很容易知道，第k级索引的结点个数就是n/(2^k)。
现在，我们假设索引有h层，最高级的索引有两个结点。可以得出，h = log(2)n - 1。如果包含原始层的话，那跳表的高度就是log(2)n。接下来我们再假设在每一层都要遍历m个结点。这个m怎么计算呢？先来思考一下，从第一层到第h层，我们都是每隔两个结点往上取一个。观察一下会发现，上一层两个结点对应下一层是三个结点，也就是说每两层之间，最多会遍历三个结点。如果你还没明白，你可以参照上面较多数据的那张图再看看。
所以我们就可以得出，当我们每两个结点往上取一个结点索引，最高索引有两个结点，我们最终得到的时间复杂度是O(logn)。
过去也学习了好几课了，当我看到这个跳表的时候，第一反应就是，这不就是用空间来换时间嘛？这空间复杂度看起来也不会很低啊？那会不会得不偿失啊？老师接下来就给出了答案。
跳表是不是很浪费内存？
前面建立那么多的索引，我们都是要存起来的，那它到底会消耗多少额外的空间呢？
我们前面分析了，当每两个结点取一个索引，它的每一层是一个等比为1/2，首项n/2，末项为2的等比数列，那么我们求个和空间复杂度就出来了，就是：n/2 + n/4 + n/8 + … + 4 + 2 = n - 2。所以跳表的空间复杂度是O(n)。那你可能会有意见了，我本来链表就有n个结点，现在又要花一倍的空间来存索引？那我们有没有办法来降低它占用的内存空间呢？
你可能已经想到了，空间复杂度是根据每两个结点(结点差值)往上取得出来的。那当我每三个往上取一个，或者每四个往上去一个，那等比的总和不就小了嘛？聪明！就是这样。但是我们可以想象的到，如果数据量特别大，而我们取得结点差值又很大。比如现在有从1000个有序的数据，我想找到第899(假设它就在第899的位置上)这个数，结果你的结点差值是100，那我遍历了8次到了800却还要遍历99次才能找到这个数。所以，我们要根据实际情况来取结点差值。
实际上，软件开发中 我们不必太在意索引占用的空间。在学习这么课的时候，我们习惯性的把要处理的数看成整数，但是在实际的软件开发中，原始链表中存储的可能是很大的对象，而索引结点只需要存储关键值和几个指针。所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。
高效的动态插入和删除
当然，跳表也不仅仅只是能提高查询某一个结点的效率，它还支持快速的添加和删除操作。我们知道，链表删除某个已知结点的时间复杂度是O(1)，而跳表的查询结点时间复杂度是O(logn)。所以，当我们使用跳表就可以实现时间复杂度为O(logn)的删除和添加操作了。
跳表索引动态更新
当我们不停往跳表中插入数据还不更新索引，就有可能导致两个索引之间的数据非常的多。极端的情况下还会退化成单链表。
作为一种动态数据结构，我们需要某种手段来维护索引与原始数据链表大小之间的平衡。如果链表中结点多了，索引结点就应该相应的增加一些，避免复杂度退化。
如果你了解红黑树、AVL树这样的平衡二叉树，你就知道它们是通过左右旋的方式保持左右子树的大小平衡，而 跳表是通过随机函数来维护前面提到的平衡性。
当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。那我们应该插入到哪些层呢？我们通过一个随机函数来决定将这个结点插入到哪几层里去。比如随机函数生成了值k，那我们就将这个结点添加到第一级到第k级这k层索引里边去。这样：
老师在这里又提到了红黑树、AVL树这些平衡二叉树，好叭，我又不会，那就再立个flag吧。等我学会了这些乱七八糟的树我还会再回来的！！！
解答开篇
问题是：为什么Redis要用跳表来实现有序集合，而不是红黑树呢？
Redis中的有序集合是通过跳表来实现的，严格点讲，其实还用到了散列表。如果查看redis开发手册会发现，redis中的有序集合支持的核心操作主要有：
- 插入一个数据
- 删除一个数据
- 查找一个数据
- 按照区间查找数据
- 迭代输出有序序列
其中，插入、删除、查找以及迭代输出有序序列，红黑树也可以完成，时间复杂度和跳表一样。但是按照区间来查找数据这个操作，红黑树的效率没有跳表高。
对于按照区间查找数据这个操作，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。
当然，redis之所以用跳表来实现有序集合还有其它的原因。比如，相比于红黑树，跳表的代码看起来更易于理解、可读性更好也不容易出错。而且跳表也更加的灵活，他可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
不过，跳表也不能完全代替红黑树。红黑树比跳表出现的更早一些，很多编程语言中的Map类型都是基于红黑树实现的，当我们做业务开发的时候直接拿来用就好了，但是对于跳表我们就需要手动实现了。
内容小结
我们今天说来跳表这种数据结构。跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的”二分查找”。跳表也是一种动态的数据结构，支持快速的插入、删除、查找操作，时间复杂度都是O(logn)。
跳表的空间复杂度是O(n)。不过它可以通过改变索引的构建策略，有效平衡执行效率和内存消耗。
课后思考
在今天的内容中，对于跳表的时间复杂度分析，我分析了每两个结点提取一个节点作为索引的时间复杂度。如果每三个或者每五个结点提取一个结点作为上级索引，对应的跳表中查询数据的时间复杂度是多少呢？
@leo
跳表是我非常喜欢的数据结构，之前写过一篇文章，希望大家斧正。另外，严格来讲，Redis的对象系统中的每种对象实际上都是基于使用场景选择多种底层数据结构实现的，比如ZSET就是基于【压缩列表】或者【跳跃表+字典】（这也跟之前排序中提到的Sort包实现的思想一样，基于数据规模选择合适的排序算法），体现了Redis对于性能极致的追求。
@escray
如果每三个或者五个节点提取一个节点作为上级索引，那么对应的查询数据时间复杂度，应该也还是 O(logn)。
假设每 5 个节点提取，那么最高一层有 5 个节点，而跳表高度为 log5n，每层最多需要查找 5 个节点，即 O(mlogn)中的 m = 5，最终，时间复杂度为 O(logn)。
空间复杂度也还是 O(logn)，虽然省去了一部分索引节点，但是似乎意义不大。
不知道在一般的生产系统，跳表的提取是按照多少个节点来实现？还是每个系统根据实际情况，都不一样。
看了跳表的 Java 实现，查找部分的代码真是漂亮，插入部分看了半天才看明白。
有问题？发送 issues 给我~