一、什么是跳表
在普通链表中要查找某个元素，只能从头到尾遍历链表。这样查找的时间复杂度很高（O(n)）。为了...
一、什么是跳表
在普通链表中要查找某个元素，只能从头到尾遍历链表。这样查找的时间复杂度很高（O(n)）。为了提高查找效率，可以对链表建立“索引”。链表加多级索引的结构，就是跳表。在跳表中查询任意数据的时间复杂度为O(logn）。由于要存储索引结构，空间复杂度为O(n)，跳表利用了“空间换时间”这种思想。
跳表不仅支持查找操作，还支持动态的插入、删除操作，而且插入、删除操作的时间复杂度也是O(logn)。
![\"在这里插入图片描述\"](\"/images/csdn/15455565481cc54555Wa6548.png\")
二、为什么Redis要用跳表来实现有序集合，而不是红黑树
Redis中的有序集合支持的核心操作主要有下面这几个：
- 插入一个数据
- 删除一个数据
- 查找一个数据
- 按照区间查找数据（比如查找值[100,356]之间的数据）
- 迭代输出有序序列
对于插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，根据区间来查找数据这个操作，红黑树的效率没有跳表高。对于按照区间查找数据这个操作，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后再原始链表中顺序往后遍历就可以了。这样做非常高效。
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：过滤器入门看这一篇就够了 下一篇：过滤器应用【编码、敏感词、压缩、转义过滤器】
