2.8.1跳表简介

    二分法底层依赖是数组的随机访问性，如果将数据存储在链表中，真的没有办法来实现二分查找吗？实际上对链表进行稍微改造就可以，改造好的数据结构叫做跳表。他是一种比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以代替红黑树。Redis中的有序集合，就是通过跳表来实现的（严格上来说还有散列表），而红黑树也可以做到快速的插入，删除，查找。Redis有序集合却仍然的选择使用跳表。

    Redis有序集合主要是插入删除查找一个数据、按照区间查找数据、迭代输出有序序列。

    其中插入删除查找迭代输出操作，跳表和红黑树的时间复杂度都是O(logn)。但是按照区间查找数据这个操作，跳表要比和红黑树高效。除此以外，跳表的代码更容易实现，可读性强，跳表的实现非常灵活，可以通过构建索引策略，有效平衡执行效率和内存消耗。不过跳表也不能完全代替红黑树，因为很多编程语言中的Map都是通过红黑树去实现的，做业务开发的时候可以直接拿来用，而跳表则没有一个现成的实现，在开发中如果想要使用跳表，则需要自己实现。

    如下图，单链表要想查询一个数据，需要从头开始遍历，时间复杂度为O(n)。

    如果像图中这样，对链表建立一级索引，抽出来的这一级叫做索引或者索引层。图中down表示down指针，可以指向下一级结点。如果要找到数据为16的结点，上图需要遍历10个结点，下图需要遍历7个结点。从这个例子可以看出，加一层索引，查找效率变高了。

    在加一层索引，如果想找到16，只需要遍历6个结点了，数据量不是很多，所以对于效率的提升没那么明显。

    如下图，这时要找62结点时只需要遍历11个结点，而如果是单链表的话则需要遍历62个结点，60多个数据的时候效率可以看出来有显著的提升，而还有可能会1000，10000...个数据。

2.8.2跳表到底有多快

    跳表的时间复杂度：一个链表含有n个结点，时间复杂度是O(n)，第一层索引需要加n/2个结点，第二级就是n/4...以此类推，第k级结点的个数是n/(2k)，假设最高级的索引更有两个结点，也就是n/(2k)=2，k=log2n-1，如果包括原始链表，也就是共有k=log2n级，如果每一层遍历m个结点，那在跳表查询的时间复杂度就是O(logn)，而按照前面的这种数据结构，m的最大值也就是3。下图就可以看出来，所以跳表查询任意数据的时间复杂度就是O(logn)，和二分查找的时间复杂度是一样的，在单链表的基础上实现了二分查找，但是与此同时要建立很多的索引，这就是一种用空间换时间的设计思路。

2.8.3跳表是不是很浪费内存

    跳表的空间复杂度分析，索引依次所占的空间是n/2,n/4...4,2。所以累积起来，跳表的空间复杂度就是O(n)。

    实际上，在实际软件开发中，不必太过于在意索引占用的额外的空间。因为在实际开发中，原始链表存储的很有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引用的额外空间就可以忽略了。

2.8.4跳表的动态插入和删除

    跳表这个动态数据结构插入和删除的时间复杂度都是O(logn)，在单链表中，要插入结点的时间复杂度是O(1)，但是为了保证插入的有序性，在插入之前要先确定插入的位置，这样的话是比较费时的。对于纯粹的单链表需要遍历每个结点，来找到插入的位置。但是对于跳表来说，插入一个数据的时间复杂度和查找一样，也是O(logn)。如下图：

2.8.5跳表索引动态更新

    如果不停地向跳表中插入数据，如果不更新索引，就有可能会出现两个索引结点之间数据非常多的情况，在极端情况下跳表会退化成单链表。

    而跳表作为一种动态的数据结构，需要某种手段来维护索引和原始链表大小之间的平衡，也就是说，如果链表数据多了，索引结点就增加一些，避免查找、插入、删除操作性能下降。跳表正是通过随机函数来维护“平衡性”。

    当往跳表插入数据时，可以选择同时将这个数据插入到部分索引层，这时会通过一个随机函数，来决定将这个结点插入到那几级索引中，比如随机函数生成了k，就把值插入到第k级这k级索引中。

（本文是个人听课笔记，不少东西摘取于王争老师的原文，原文链接http://gk.link/a/10aMZ）