+
+

数据结构与算法之美:跳表

什么是「跳表」

我们知道,数组因为具有下标支持随机访问,所以对于有序数组我们可以用二分法快速查找到目标值所在的位置。而链表因为不支持随机访问,无法直接利用二分法,只需要对链表稍加改造,就可以支持类似“二分”的查找算法。改造之后的数据结构叫作跳表(Skip list),是一种各方面性能都比较优秀的动态数据结构,支持快速的插入、删除、查找操作,写起来也不复杂,甚至可以替代红黑树(Red-black tree)。Redis中的有序集合(Sorted Set)就是用跳表来实现的。

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

那怎么来提高查找效率呢?如果像图中那样,对链表建立一级「索引」,查找就会更快一些——每两个结点提取一个结点到上一级,抽出来的那一级叫作索引或索引层。下图中的down表示 down指针,指向下一级结点。

加来一层索引之后,查找一个结点需要遍历的结点个数减少了,也就是说查找效率提高了。那如果我们再加一级索引呢?效率会不会提升更多呢?

下图,原来没有索引的时候,查找 62 需要遍历 62 个结点,现在只需要遍历 11 个结点,速度是不是提高了很多?所以,当链表的长度 n 比较大时,比如 1000、10000 的时候,在构建索引之后,查找效率就会得到明显提升。

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

查找的时间复杂度

如果链表里有$n$个结点,按照我们刚才讲的,每两个结点会抽出一个结点作为上一级索引的结点,那第一级索引的结点个数大约就是$\frac{n}{2}$,第二级索引的结点个数大约就是$\frac{n}{4}$,依次类推,第$k$级索引结点的个数就是$\frac{n}{2k}$。

设索引有$h$级,最高级的索引有2个结点。通过上面的公式,我们可以得到$\frac{n}{2h}=2$,从而求得$h=\log_2n-1$。如果包含原始链表这一层,整个跳表的高度就是$\log_2n$。我们在跳表中查询某个数据的时候,如果每一层都要遍历$m$个结点,那在跳表中查询一个数据的时间复杂度就是$O(m*\log_n)$。

如果按照「下一级是下一级每两个节点提取出一个,最高级的索引层有2个结点」的索引结构,我们每一级索引都最多只需要遍历3个结点(包括y和z)。

那么$m=3$,所以在跳表中查询任意数据的时间复杂度就是$O(\log n)$。这个查找的时间复杂度跟二分查找是一样的。换句话说,我们其实是基于单链表实现了二分查找。不过,这种查询效率的提升,前提是建立了很多级索引,也就是用空间换了时间。

跳表的空间复杂度

这几级索引的结点总和就是$n-2$。所以,跳表的空间复杂度是$O(n)$。

那我们有没有办法降低索引占用的内存空间呢?我们前面都是每两个结点抽一个结点到上级索引,如果我们每三个结点或五个结点,抽一个结点到上级索引,是不是就不用那么多索引结点了呢?

通过等比数列求和公式,总的索引结点大约就是 $\frac{n}{3}+\frac{n}{9}+\frac{n}{27}+…+9+3+1=\frac{n}{2}$。尽管空间复杂度还是$O(n)$,但比上面的每两个结点抽一个结点的索引构建方法,要减少了一半的索引结点存储空间。

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

动态插入和删除

实际上,跳表这个动态数据结构,不仅支持查找操作,还支持动态的插入、删除操作,而且插入、删除操作的时间复杂度也是$O(\logn)$。

插入

为了保证原始链表中数据的有序性,我们需要先找到要插入的位置,这个查找操作就会比较耗时。

跳表查找某个结点的的时间复杂度是$O(\log n)$,所以这里查找某个数据应该插入的位置,方法也是类似的,时间复杂度也是$O(\log n)$。我画了一张图,你可以很清晰地看到插入的过程。

需要注意的是,这里的插入只在原始链表中进行了插入,并没有对索引进行更新。

删除

删除结点时,我们不仅要删除原始链表中的结点,如果这个结点在索引中也有出现,还要删除索引中的结点。因为单链表中的删除操作需要拿到要删除结点的前驱结点,然后通过指针操作完成删除。所以在查找要删除的结点的时候,一定要获取前驱结点。如果我们用的是双向链表,就不需要考虑这个问题了。

更新索引

由于之前讲的插入操作只针对原始链表插入结点,当我们不停地往跳表中插入数据时,就有可能出现某2个索引结点之间数据非常多的情况。极端情况下,跳表还会退化成单链表。

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

所以,当我们往跳表中插入数据的时候,我们可以选择同时将这个数据插入到部分索引层中。

跳表通过一个「随机函数」,来决定将这个结点插入到哪几级索引中,比如随机函数生成了值 K,那我们就将这个结点添加到第一级到第K级索引中。

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

为什么 Redis 要用跳表而不是红黑树来实现有序集合

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

  • 插入一个数据;
  • 删除一个数据;
  • 查找一个数据;
  • 按照区间查找数据;
  • 迭代输出有序序列。

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

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

当然,Redis 之所以用跳表来实现有序集合,还有其他原因,比如,跳表的代码相比红黑树更容易实现。而简单就意味着可读性好,不容易出错。还有,跳表更加灵活,它可以通过改变索引构建策略,有效平衡执行效率和内存消耗。

不过,跳表也不能完全替代红黑树。因为红黑树比跳表的出现要早一些,很多编程语言中的 Map 类型都是通过红黑树来实现的。我们做业务开发的时候,直接拿来用就可以了,不用费劲自己去实现一个红黑树,但是跳表并没有一个现成的实现,所以在开发中,如果你想使用跳表,必须要自己实现。

本文作者: rhinoc

本文链接: https://www.rhinoc.top/cid216_10/

版权声明: 本博客所有文章除特别声明外,均采用BY-NC-SA 4.0国际许可协议,转载请注明。

打赏
Love U 3000
  • Through WeChat
  • Through Alipay
0%