两节我们讲了二分查找算法。当时我讲到，因为二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找算法了吗？
实际上，我们只需要对链表稍加改造，就可以支持类似“二分”的查找算法。我们把改造之后的数据结构叫作跳表（Skiplist），也就是今天要讲的内容。
跳表这种数据结构对你来说，可能会比较陌生，因为一般的数据结构和算法书籍里都不怎么会讲。但是它确实是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，
写起来也不复杂，甚至可以替代红黑树（Red-blacktree）。
Redis中的有序集合（Sorted Set）就是?跳表来实现的。如果你有一定基础，应该知道红黑树也可以实现快速的插入、删除和查找操作。那Redis为什么会选择用跳表来实现有序集合呢？
为什么不用红黑树呢？学完今天的内容，你就知道答案了。
跳表的实现还是稍微有点复杂的，我将Java实现的代码放到了GitHub中，你可以根据我刚刚的讲解，对照着代码仔细思考?下。你不?死记硬背代码，跳表的实现并不是我们这节的重点
今天我们讲了跳表这种数据结构。跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是O(logn)。
跳表的空间复杂度是O(n)。不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单，但是作为一种动态数据结构，比起红黑树来说，
实现要简单多了。所以很多时候，我们为了代码的简单、易读，比起红黑树，我们更倾向用跳表。
在今天的内容中，对于跳表的时间复杂度分析，我分析了每两个结点提取一个结点作为索引的时间复杂度。如果每三个或者五个结点提取一个结点作为上级索引，
对应的在跳表中查询数据的时间复杂度是多少呢
如果每三个或者五个节点提取一个节点作为上级索引，那么对应的查询数据时间复杂度，应该也还是 O(logn)。
假设每 5 个节点提取，那么最高一层有 5 个节点，而跳表高度为 log5n，每层最多需要查找 5 个节点，即 O(mlogn) 中的 m = 5，最终，时间复杂度为 O(logn)。
空间复杂度也还是 O(logn)，虽然省去了一部分索引节点，但是似乎意义不大。
不知道在一般的生产系统，跳表的提取是按照多少个节点来实现？还是每个系统根据实际情况，都不一样。
看了跳表的 Java 实现，查找部分的代码真是漂亮，插入部分看了半天才看明白。
原文：https://www.cnblogs.com/luoahong/p/11864974.html