跳表

因为二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。

如果数据存储在链表中，如何使用二分查找算法呢？实际上，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。改造之后的数据结构叫作跳表（Skip list）。

跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。

Redis 中的有序集合（Sorted Set）就是用跳表来实现的。红黑树同样也可以实现快速的插入、删除和查找操作。那 Redis 为什么会选择用跳表来实现有序集合呢？

Redis 中的有序集合支持的核心操作主要有下面这几个：

• 插入一个数据；

• 删除一个数据；

• 查找一个数据；

• 按照区间查找数据（比如查找值在[100, 356]之间的数据）；

• 迭代输出有序序列。

其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。

对于按照区间查找数据这个操作，跳表可以做到 $O(logn)$ 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。

其他原因：

• 跳表更容易代码实现

• 虽然跳表的实现也不简单，但比起红黑树还是好懂、好写，简单就意味着可读性好，不容易出错

• 跳表更加灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗

跳表也不能完全替代红黑树。

• 红黑树比跳表的出现要早一些，很多编程语言中的 Map 类型都是通过红黑树来实现的，拿来就用

• 跳表并没有一个现成的实现，在开发中，必须自己实现

跳表定义

对于一个单链表，即使链表中存储的数据是有序的，如果要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 $O(n)$。

为了提高查找效率，如下图所示，对链表建立一级“索引”，查找起来就会更快一些，每两个结点提取一个结点到上一级，把抽出来的那一级叫作索引或索引层。图中的down指针，指向下一级结点。

此时要查找16，首先遍历索引层，读取到13和下一个节点17，定位到16的位置，在读取13的down指针后读取到16节点。 从原来访问单链表的10个节点减少为访问7个节点。

进一步优化，在第一级索引的基础上再每两个节点提取一个第二级索引，如下图所示。

带二级索引的跳表

此时还是查找16,首先遍历第二级索引，读取到13节点，然后读取down指针，读取到17节点，定位到16节点的位置，再读取down指针，后读取到16节点。

访问节点数又下降一个，所以随着链表节点数的增加，不断增加索引级别，访问效率会有很大提高。这种链表加上多级索引的结构，就是跳表。

时间复杂度

在一个单链表中查询某个数据的时间复杂度是 $O(n)$。

索引的生成规则是每两个节点就提取一个节点作为上一级索引的节点。

• 第一级索引的节点数：$\frac{n}{2}$

• 第二级索引的节点数：$\frac{n}{4}$

• 第三级索引的节点数：$\frac{n}{8}$

• 依此类推

• 第k级索引的节点数：$\frac{n}{2^k}$

假设索引共有h级，最高级索引有2个节点，根据上面推导$\frac{n}{2^h}=2$，得到$h=log_2{(n-1)}$，加上原始链表这一次层，整个跳表的高度数$log_2{n}$。

在跳表中查询某个数据时，如果每一层都要遍历m个结点，则时间复杂度是$O(m*logn)$。

假设要查找的数据是 x：

1. 在第 k 级索引中，遍历到 y 结点之后，发现 x 大于 y，小于后面的结点 z

2. 通过 y 的 down 指针，从第 k 级索引下降到第 k-1 级索引

3. 在第 k-1 级索引中，y 和 z 之间只有 3 个结点（包含 y 和 z），所以，在 K-1 级索引中最多只需要遍历 3 个结点

4. 依次类推，每一级索引都最多只需要遍历 3 个结点

跳表的查找操作

通过上面的分析，得到 m=3，所以在跳表中查询任意数据的时间复杂度就是 $O(logn)$。

这个查找的时间复杂度跟二分查找是一样的，因此，基于单链表就实现了二分查找。虽然这种查询效率的提升，但前提是建立了很多级索引，这是一种空间换时间的设计思路。

空间复杂度

跳表需要存储多级索引，空间复杂度比较高：

• 原始链表节点数：$n$

• 第一级索引的节点数：$\frac{n}{2}$

• 第二级索引的节点数：$\frac{n}{4}$

• 依此类推

• 第k级索引的节点数：$\frac{n}{2^k}$

每上升一级，节点数就减半，直到剩下2个节点，每一层的节点数是一个等比数列。所以，全部索引的节点数总和是$\frac{n}{2}+\frac{n}{4}+\frac{n}{8}…+8+4+2=n-2$，得到跳表的空间复杂度是$O(n)$，相比于单链表需要的存储空间翻了一倍。

如果每3个节点提取一个结点到上级索引，那么：

• 第一级索引的节点数：$\frac{n}{3}$

• 第二级索引的节点数：$\frac{n}{9}$

• 依此类推

• 第k级索引的节点数：$\frac{n}{3^k}$

通过等比数列求和公式，总的索引结点大约就是 $\frac{n}{3}$+$\frac{n}{9}$+$\frac{n}{27}$+…+9+3+1=$\frac{n}{2}$。虽然空间复杂度还是$O(n)$，但是相对于上面那种构建索引的方法，存储空间节约了一半。

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

高效的动态插入和删除

跳表的动态插入和删除的时间复杂度是$O(logn)$。

插入

1. 单链表在确定位置后插入操作的时间复杂度是$O(1)$

2. 跳表为了保证有序性，需要先遍历链表，确定待插入的位置这个时间复杂度是$O(logn)$

3. 确定位置后以时间复杂度$O(1)$插入数据，此时先忽略更新索引

删除

删除的过程与上面类似，只是需要如果待删除的节点刚好在索引上，那么除了删除原始链表中的节点，还需要在索引中将该节点删除。

在遍历获取删除节点位置时，需要记录前驱节点的指针，如果是双链表就没这个问题。

索引动态更新

向跳表中不断添加数据的过程中，如果不更新索引，就会出现某2个索引节点之间的数据过多，极端情况，跳表就退化成单链表了。

跳表作为一种动态数据结构，需要某种手段来维护索引与原始链表大小之间的平衡，即如果链表中节点多了，索引节点也相应地增加一些，避免复杂度退化，以及查找、插入和删除操作性能下降。

红黑树、AVL树这样平衡二叉树，通过左右旋的方式保持左右子树的大小平衡，而跳表是通过随机函数来维护“平衡性”。

当向跳表中插入数据的时候，选择同时将这个数据插入到部分索引层中。通过一个随机函数，来决定将这个结点插入到哪几级索引中，如随机函数生成了值 K，那就将这个结点添加到第一级到第 K 级这 K 级索引中。

跳表索引的动态更新

随机函数的选择很有讲究，从概率上来讲，能够保证跳表的索引大小和数据大小平衡性，不至于性能过度退化。

至于随机函数的选择，参见 Redis 中关于有序集合的跳表实现。