数据结构学习笔记五（跳表）

一、什么是跳表

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

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

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

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

插入一个数据

删除一个数据

查找一个数据

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

迭代输出有序序列

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!