Appearance
跳表
跳表是一种各方面性能都比较优秀的动态数据结构,可以支持快速的插入、删除和查找操作。在二分查找的时候,说到它不能使用链表,实际上,将它改造为跳表,就可以支持类似“二分”的查找算法。
Redis 中的有序集合(Sorted Set)就是用跳表来实现的。如果你有一定基础,应该知道红黑树也可以实现快速的插入、删除和查找操作。那 Redis 为什么会选择用跳表来实现有序集合呢? 为什么不用红黑树呢?
理解跳表
对于单链表来说,即便存储的数据是有序的,也只能通过遍历来查找某个数据。查找的时间复杂度为 O(n),效率并不高。
单链表查询慢是因为需要从头遍历,那么对链表建立一级索引,查找就会快起来。这里每两个结点取一个到上一级,把抽出来的这一级叫作索引或者索引层。其中,down 表示 down 指针,指向下一级结点。
如果我们要查找值为 14 这个结点,通过单链表,需要遍历 10 个结点。
而使用了跳表之后,可以现在索引层遍历,当遍历到值为 13 的这个结点时,我们发现下一个结点值为 15,所以 14 肯定在这两个结点之间。通过 down 指针,下降到原始数据这一层,继续遍历,这个时候只需要遍历 2 个结点,就找到值为 14 的结点了。总共遍历 7 个结点。
也就说,加了一层索引层之后,查找一个结点需要遍历的结点少了,效率提高了。
跟前面类似,可以依次在索引上继续增加索引层。
加了第二级所以之后,现在只需要遍历 6 个结点。
这里数据量不大,所以提升的效率不是很明显。当链表的长度为 100、1000 等,通过构建索引,查询效率会得到极大的提升。
这种链表加多级索引的结构,就是跳表。
时间复杂度
通过添加索引层,可以提高查询的效率。下面算一下跳表的时间复杂度。
上面简历索引是每 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
这是一个等比数列,根据等比数列的求和公式:
可以求得需要的总结点数为 Sn = n - 2,所以跳表的空间复杂度是 O(n)。
上面都是每 2 个结点抽一个到上级作为索引,那如果每 3 个或者每 5 个呢?
以每 3 个结点抽一个再分析一遍:
- 的时间复杂度
n/3, n/9, ..., n/3^k, ...
总共有 h 级,那么 n/3^h = 3,h = log3n - 1,每一级最多遍历 4 个结点所以时间复杂度为 O(4*(log3n-1)),即 O(logn)。
- 空间复杂度
n/3, n/9, ..., 9, 3, 1
根据等比数列的求和 Sn = n/2。尽管空间复杂度还是 O(n),但比上面的每两个结点抽一个结点的索引构建方法,要减少了一半的索引结点存储空间。
实际上,在软件开发中,我们不必太在意索引占用的额外空间。在讲数据结构和算法时,习惯性地把要处理的数据看成整数,但是在实际的软件开发中,原始链表中存储的有可能是很大的对象,而索引结点只需要存储关键值和几个指针,并不需要存储对象,所以当对象比索引结点大很多时,那索引占用的额外空间就可以忽略了。
高效的插入和删除
跳表是个动态的数据结构,不仅支持查询,还支持动态的插入和删除。而且插入和删除的复杂度也是 O(logn)。
单链表的插入和删除操作复杂度都是 O(1),而跳表的查找某个结点时间复杂度是 O(logn),现在要查找某个数据应该插入和删除的位置,要找到前驱结点,方法也类似,所以时间复杂度是 O(logn)。
值得注意的时,删除某个结点时,如果这个节点也存在于索引中,那么还要将索引中的结点删除。
跳表的动态性
当我们不停的向跳表中插入数据,如果不更新索引,就可能出现 2 个索引节点之间的数据非常多的情况。极端情况下,跳表还会退化为单链表。
为了避免退化,保持索引和原始链表大小之间的平衡,那么链表结点增加了,索引结点也需要增加。
跳表是通过随机函数来维护这个平衡的。通过一个随机函数,来决定将这个结点插入到哪几级索引。比如,随机生成函数生成 k,那么就将节点插入 1~k 级这 k 级索引中。
随机函数,从概率上保证跳表的索引和数据的大小平衡。
总结
解答开篇
先解答开篇,Redis 为什么会选择用跳表来实现有序集合呢?
Redis 中的有序集合是通过跳表来实现的,严格点讲,其实还用到了散列表。我们知道Redis 中的有序集合支持的核心操作主要有下面这几个:
- 插入一个数据;
- 删除一个数据;
- 查找一个数据;
- 按照区间查找数据(比如查找值在 [100, 356] 之间的数据);
- 迭代输出有序序列。
其中,插入、删除、查找以及迭代输出有序序列这几个操作,红黑树也可以完成,时间复杂度跟跳表是一样的。但是,按照区间来查找数据这个操作,红黑树的效率没有跳表高。
对于按照区间查找数据这个操作,跳表可以做到 O(logn) 的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了。这样做非常高效。
当然,Redis 之所以用跳表来实现有序集合,还有其他原因,比如,跳表更容易代码实现。虽然跳表的实现也不简单,但比起红黑树来说还是好懂、好写多了,而简单就意味着可读性好,不容易出错。
还有,跳表更加灵活,它可以通过改变索引构建策略,有效平衡执行效率和内存消耗。
小结
跳表这种数据结构使用的是空间换时间的思路,通过构建多级索引来提高查询效率,实现了基于链表的“二分查找”(时间复杂度是 O(logn))。
跳表是一种动态的数据结构,支持快速插入、删除和查找操作,时间复杂度都是 O(logn)。
跳表作为一种数据结构,它需要额外的存储空间来存储索引层,空间复杂度是 O(n)。不过,跳表的实现非常灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗。
虽然跳表的代码实现并不简单,但是作为一种动态数据结构,比起红黑树来说,实现要简单多了。所以很多时候,我们为了代码的简单、易读,比起红黑树,倾向用跳表。