C# · 12月 20, 2021

数据结构学习笔记五(跳表)

一、什么是跳表

在普通链表中要查找某个元素,只能从头到尾遍历链表。这样查找的时间复杂度很高(O(n))。为了提高查找效率,可以对链表建立“索引”。链表加多级索引的结构,就是跳表。在跳表中查询任意数据的时间复杂度为O(logn)。由于要存储索引结构,空间复杂度为O(n),跳表利用了“空间换时间”这种思想。

跳表不仅支持查找操作,还支持动态的插入、删除操作,而且插入、删除操作的时间复杂度也是O(logn)。

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

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

插入一个数据

删除一个数据

查找一个数据

按照区间查找数据(比如查找值[100,356]之间的数据)

迭代输出有序序列

对于插入、删除、查找以及迭代输出有序序列这几个操作,红黑树也可以完成,时间复杂度跟跳表是一样的。但是,根据区间来查找数据这个操作,红黑树的效率没有跳表高。对于按照区间查找数据这个操作,跳表可以做到O(logn)的时间复杂度定位区间的起点,然后再原始链表中顺序往后遍历就可以了。这样做非常高效。