🎧 fe tutorial

Appearance

Return to top
On this page

跳表

跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除和查找操作。在二分查找的时候，说到它不能使用链表，实际上，将它改造为跳表，就可以支持类似“二分”的查找算法。

Redis 中的有序集合（Sorted Set）就是用跳表来实现的。如果你有一定基础，应该知道红黑树也可以实现快速的插入、删除和查找操作。那 Redis 为什么会选择用跳表来实现有序集合呢？ 为什么不用红黑树呢？

理解跳表

对于单链表来说，即便存储的数据是有序的，也只能通过遍历来查找某个数据。查找的时间复杂度为 O(n)，效率并不高。

skipList-linked

单链表查询慢是因为需要从头遍历，那么对链表建立一级索引，查找就会快起来。这里每两个结点取一个到上一级，把抽出来的这一级叫作索引或者索引层。其中，down 表示 down 指针，指向下一级结点。

skipList-oneLay

如果我们要查找值为 14 这个结点，通过单链表，需要遍历 10 个结点。

而使用了跳表之后，可以现在索引层遍历，当遍历到值为 13 的这个结点时，我们发现下一个结点值为 15，所以 14 肯定在这两个结点之间。通过 down 指针，下降到原始数据这一层，继续遍历，这个时候只需要遍历 2 个结点，就找到值为 14 的结点了。总共遍历 7 个结点。

也就说，加了一层索引层之后，查找一个结点需要遍历的结点少了，效率提高了。

跟前面类似，可以依次在索引上继续增加索引层。

skipList-twoLays

加了第二级所以之后，现在只需要遍历 6 个结点。

这里数据量不大，所以提升的效率不是很明显。当链表的长度为 100、1000 等，通过构建索引，查询效率会得到极大的提升。

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

skipList-threeLays

时间复杂度

通过添加索引层，可以提高查询的效率。下面算一下跳表的时间复杂度。

上面简历索引是每 2 个结点抽出一个作为上一级的索引结点。所以有：

// 第一级索引的结点个数大约
n/2

// 第二级索引的结点个数大约
n/4

// 第三级索引的结点个数大约
n/8
...
// 第k级索引的结点个数大约
n/2^k
...

现在总共有 h 级索引，而最高级索引有 2 个结点。那么就有 n/2^h = 2，h = log2n - 1。如果包含原始数据这层，整个跳表的高度就是 log2n。

现在查找某个数据，如果每层需要遍历 m 个结点，那么跳表查询一个数据的时间复杂度就是 O(m * log2n)，即 O(m * logn)。

现在只需要知道 m 是多少就可以知道时间复杂度了。

跳表的某一级索引都是在下一级的每 2 个结点抽出一个结点组成的。所以当我们从 k 级降到 k-1 级，在 k-1 级最多遍历不会超过 3 个结点。得到 m = 3。

最后就得到跳表的时间复杂度就是 O(logn)。非常高效，时间复杂度和二分查找一样，也就是说基于单链表实现了二分查找。

空间复杂度

跳表是通过建立索引来提升效率，以空间换时间。分析以下它的空间复杂度。

原始链表长度为 n，每 2 个节点抽 1 个，那么第一级索引大约需要 n/2 个结点，第二级大约需要 n/4 个结点，...，最高一级需要 2 个结点。所以每一级需要的节点如下：

n/2, n/4, n/8, ..., 8, 4, 2

这是一个等比数列，根据等比数列的求和公式：

math

可以求得需要的总结点数为 Sn = n - 2，所以跳表的空间复杂度是 O(n)。

上面都是每 2 个结点抽一个到上级作为索引，那如果每 3 个或者每 5 个呢？

以每 3 个结点抽一个再分析一遍：

  1. 的时间复杂度
n/3, n/9, ..., n/3^k, ...

总共有 h 级，那么 n/3^h = 3，h = log3n - 1，每一级最多遍历 4 个结点所以时间复杂度为 O(4*(log3n-1))，即 O(logn)。

  1. 空间复杂度
n/3, n/9, ..., 9, 3, 1

根据等比数列的求和 Sn = n/2。尽管空间复杂度还是 O(n)，但比上面的每两个结点抽一个结点的索引构建方法，要减少了一半的索引结点存储空间。

实际上，在软件开发中，我们不必太在意索引占用的额外空间。在讲数据结构和算法时，习惯性地把要处理的数据看成整数，但是在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。

高效的插入和删除

跳表是个动态的数据结构，不仅支持查询，还支持动态的插入和删除。而且插入和删除的复杂度也是 O(logn)。

单链表的插入和删除操作复杂度都是 O(1)，而跳表的查找某个结点时间复杂度是 O(logn)，现在要查找某个数据应该插入和删除的位置，要找到前驱结点，方法也类似，所以时间复杂度是 O(logn)。

值得注意的时，删除某个结点时，如果这个节点也存在于索引中，那么还要将索引中的结点删除。

跳表的动态性

当我们不停的向跳表中插入数据，如果不更新索引，就可能出现 2 个索引节点之间的数据非常多的情况。极端情况下，跳表还会退化为单链表。

multipleInsert

为了避免退化，保持索引和原始链表大小之间的平衡，那么链表结点增加了，索引结点也需要增加。

跳表是通过随机函数来维护这个平衡的。通过一个随机函数，来决定将这个结点插入到哪几级索引。比如，随机生成函数生成 k，那么就将节点插入 1~k 级这 k 级索引中。

随机函数，从概率上保证跳表的索引和数据的大小平衡。

总结

解答开篇

先解答开篇，Redis 为什么会选择用跳表来实现有序集合呢？

Redis 中的有序集合是通过跳表来实现的，严格点讲，其实还用到了散列表。我们知道Redis 中的有序集合支持的核心操作主要有下面这几个：

  • 插入一个数据；
  • 删除一个数据；
  • 查找一个数据；
  • 按照区间查找数据（比如查找值在 [100, 356] 之间的数据）；
  • 迭代输出有序序列。

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

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

当然，Redis 之所以用跳表来实现有序集合，还有其他原因，比如，跳表更容易代码实现。虽然跳表的实现也不简单，但比起红黑树来说还是好懂、好写多了，而简单就意味着可读性好，不容易出错。

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

小结

跳表这种数据结构使用的是空间换时间的思路，通过构建多级索引来提高查询效率，实现了基于链表的“二分查找”（时间复杂度是 O(logn)）。

跳表是一种动态的数据结构，支持快速插入、删除和查找操作，时间复杂度都是 O(logn)。

跳表作为一种数据结构，它需要额外的存储空间来存储索引层，空间复杂度是 O(n)。不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。

虽然跳表的代码实现并不简单，但是作为一种动态数据结构，比起红黑树来说，实现要简单多了。所以很多时候，我们为了代码的简单、易读，比起红黑树，倾向用跳表。

Edit this page on GitHub