二分查找的底层依赖的是数组随机访问的特性，那么如果数据存在链表中，我们就无法进行二分查找了吗？事实上是阔以滴。比如Redis就是通过跳表来实现的。它是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作。但是红黑树也可以呀，哼，你跳表可以的，我红黑树也可以呢！

        为什么Redis使用了跳表，而没有用红黑树，继续往下看~

    1如何理解跳表

        如下图，对于一个单链表来说，即便是最好的情况——它里面存储的元素都是有序的，但是查找某一个元素也需要一个一个从头到尾遍历链表元素，直到找到它，时间复杂度是比较高的，要O(n)呢~这样查找效率就比较低~

        那么如何提高它的查找效率呢？我们可以采用提取索引的方式，每两个节点提取一个索引到上一级，我们把抽出来的那一级叫做索引或者索引层。其中down是指针，指向下一个索引~

        现在我们要查找某一个节点，比如说16，我们先遍历索引节点1、4、7、9、13、17，发现13<16,17>16，此时就不用继续往后遍历索引，只需遍历节点13与节点17之间的元素即可。原始链表按顺序从头到尾需要遍历10个节点，提取索引之后我们只需遍历7个节点就好啦。

        上面我们只提取了一层索引，我们把它叫做一级索引。

        我们在第一级索引的基础上，还可以提取出二级索引，如下图：

        这样遍历的节点个数就又变少啦。

        我们这个例子中的数据量不大，可能看不出跳表的优势，实际上它在大数据量面前是非常高效滴。

        比如下面画了一个5级索引的图：

        显而易见速度提高了灰常多。当这个维度更大时，跳表的优势也更加明显。

        这种链表加多级索引的结构，就是跳表。

    2跳表查询到底有多快？

        衡量速度的标准当然是时间复杂度啦。

        下面我们来分析一下跳表的时间复杂度。

        假设链表中有n个元素，那么一级索引有n/2个元素，二级索引有n/4个元素，三级索引有n/8个元素，依次类推，k级索引有n/2^k个元素。

        假设索引一共有h级，最高级的索引有2个节点，那么n/2^h=2，log(2)n=h+1，h=log(2)n-1。如果包含原始链表层，我们的整个跳表高度就是log(2)n。

        如果每一层要遍历的节点个数是m，那么跳表中查询一个元素的时间复杂度就是O（m*logn）。在这里，我们的m值为3。为啥是3捏？因为从最顶层索引开始，最顶层索引只有2个，并且每两个索引之间（包括它自己）只有一共三个节点，所以当然最多才是3啦。可以参考着下图来思考：

        综上，在跳表中查询任意元素的时间复杂度为O(logn)。这和二分查找是一样哒。

        但是，高的时间效率也是在其他方面有做牺牲的——空间。因为它建立了许多索引，需要额外的存储空间，这就是空间换时间的设计思路。

    3跳表是不是很浪费内存？

        说内存，我们就要算一算时间复杂度啦。

        第一层索引有n/2个，第二层有n/4个，依次类推，最后一层有2个：

        我们把它们加起来，总和是n-2。所以，跳表的空间复杂度是O(n)。

        我们也有办法稍微降低一下存储空间，隔3个、5个节点抽取一个索引。这样空间复杂度得到了一些降低，而时间复杂度还是O(logn)。（因为只是将m从3换成了其他常数）

        但是，在软件开发中，我们不必太在意索引占用的额外空间。因为在实际开发中，原始链表中存储的可能是很大的对象，而索引节点只需要存关键字和指针，当对象比索引节点大很多的情况下时，索引占用的额外空间就可以忽略了。

    4高效的动态插入和删除

        跳表除了可以进行高效的查找，也可以进行高效的插入和删除。

        首先说插入，很好理解，通过查找操作找到要插入的位置，时间复杂度是O(logn)，然后进行插入操作，时间复杂度是O(1)，可忽略不计。所以插入的时间复杂度也是O(logn)。

        然后是删除，也是先通过查找操作找到要删除的位置，不过这里注意我们还需要获取删除位置的前驱节点（双向链表就无需额外考虑这个问题啦），另外还要注意的是，如果这个元素在索引中出现了，我们也要将索引删掉哦。删除操作的时间复杂度也是O(logn)。

    5跳表索引动态更新

        当对链表进行不断的插入操作之后，就会出现这样的情况，如下图所示，两个索引之间的元素变得非常多，甚至退化回了单链表：

        跳表是通过动态函数来维护这个平衡性的。

        通过动态函数生成一个随机数K，在向链表中插入某个数时，同时也会将它插入第1-K层索引中去。从随机概率的角度来讲，这样就维护了跳表的平衡性。如下图所示：

    6解答开篇

        之所以Redis没有用红黑树而用了跳表，是因为Redis有一个按照区间查找数据的操作，通过跳表可以做到用O(logn)的时间复杂度找到区间的起点，然后依次往下遍历就好啦，它的代码实现相对红黑树更加好懂、好写、可读性好、不易出错（虽然跳表的实现也不简单，哼哼o(￣ヘ￣o＃)）。

        当然，跳表也不能完全取代红黑树啦。作为比跳表出现更早的红黑树，在很多编程语言中的Map类型都是通过红黑树来实现的，我们可以直接拿来用，如果用调表的话，我们需要自己实现。

    7内容小结

        跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是O(logn)。

        跳表的空间复杂度是O(n)。不过跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单，但是作为一种动态数据结构，比起红黑树来说，实现要简单多啦。所以很多时候，我们为了代码的简单、易读，比起红黑树，我们更倾向于链表。