定义：
跳表使用空间换时间的设计思路，
通过为有序链表构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。
跳表是一种动态数据结构，支持快速地插入、删除、查找操作。
比如对一个有序的链表，每2个节点提取一个节点到上一级，我们把抽出来的那一级叫做索引或索引层。其中索引层节点包含一个down指针，指向下一级节点。以此类推，对于节点数为n的链表，大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构就称为跳表。
时间、空间复杂度
查询时间复杂度都是 O(logn)，
空间复杂度是O(n)。
跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗，在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。
插入和删除
跳表本质上就是链表，所以仅插入和删除操作的时间复杂度就为O(1)，但在实际情况中，要插入或删除某个节点，需要先查找到指定位置，而这个查找操作比较费时，但在跳表中这个查找操作的时间复杂度是O(logn)，所以，跳表的插入和删除操作的是时间复杂度也是O(logn)。
跳表索引动态更新？
当往跳表中插入数据的时候，可以选择同时将这个数据插入到部分索引层中，那么如何选择这个索引层呢？可以通过随机函数来决定将这个节点插入到哪几级索引中，比如随机函数生成了值K，那就可以把这个节点添加到第1级到第K级索引中。
为什么Redis一定要用跳表来实现有序集合？
Redis 中的有序集合支持的核心操作主要有下面这几个：
插入一个数据；
删除一个数据；
查找一个数据；
按照区间查找数据（比如查找值在[100, 356]之间的数据）；
迭代输出有序序列。
1、其他都也可以使用红黑树来实现，但是其中按照区间来查找数据这个操作，红黑树的效率没有跳表高。而跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。
2、而且跳表更容易代码实现。可读性好，不容易出错，更加灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
网友评论