我们都知道，对于链表的查找，时间复杂度为O(n)，那么有没有什么办法来提高查找性能呢？
答案是肯定的，需要对链表进行一些改造，改造方法就是我们向上提取一层数据，即每间隔x个节点，向上提取一个数，作为索引，如下
原始数据：
1 2 3 4 5 6 7 8 9 10 15 18 20
每两个数字就提取一个节点：
1 3 5 7 9 15 20
^ ^ ^ ^ ^ ^ ^
| | | | | | |
1 2 3 4 5 6 7 8 9 10 15 18 20按照上面的形式，形成的数据结构，叫做跳表（Skip list）。
查找数据时，我们先遍历索引，能够很快就定位到要查找的数据所在的范围，例如我查找8，那么先遍历索引层的数据，发现8再7和9中间，那么就从节点7向下，开始遍历，那么就找到了8。
那么遍历的节点依次是：1>3>5>7>8
如果不使用跳表，从链表开头依次遍历节点1>2>3>4>5>6>7>8
对比看出，跳表的遍历明显少于普通的遍历，当一个链表特别大的时候，跳表的效率就会非常明显的体现出来。
给链表加索引不仅限加一级，可以加多级，并且也不是必须每两个数提取一个数作为索引，可以3个数，或者5个数提取一个数作为索引。
简单总结就是：给链表加多级索引后，就形成了跳表。
跳表查找的时间复杂度就是 O(logn)。
跳表的空间复杂度是多少呢？
因为跳表要存储多级索引，所以空间复杂度肯定不是O(1)。
如果我们每两个节点提取一个数作为索引，那么可以推导第一级索引数量是n/2，第二级索引数量是n/4，依次类推。
这就是一个等比数列，最终几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。
所以跳表的空间复杂度是O(n)。
跳表的插入和删除
当我们往链表中插入或删除数据的时候，在找到对应位置后，插入或删除的时间复杂度是O(1)，但是查找的时间复杂度是O(n)。
但在跳表中，插入或删除的时间复杂度结合查找，最终的时间复杂度还是O(logn)，因为最耗时的还是查找。
跳表的更新
既然跳表支持插入和删除，那么就有可能两个索引节点中间的数据插入或删除较多，那么在这一段数据段中，查找数据就退化成了链表的查找效率，这时候，就需要更新索引了。
当往跳表中插入数据时，可以通过随机函数来维护前面提到的“平衡性”。
通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值N，那我们就将这个结点添加到第一级到第N级这N级索引中。
总结：跳表是一种动态数据结构，支持快速地插入、删除、查找操作，时间复杂度都是 O(logn)。