跳表是一种动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。Redis 中的有序集合（Sorted Set）就是用跳表来实现的。
链表加多级索引的结构，就是跳表。
在一个单链表中查询某个数据的时间复杂度是 O(n)。那在一个具有多级索引的跳表中查询任意数据的时间复杂度是 O(logn)。这
个查找的时间复杂度跟二分查找是一样的。换句话说，我们其实是基于单链表实现了二分查找。（这种查询效率的提升，前提是建立了很多级索引，也就是空间换时间的设计思路。）
跳表的空间复杂度是O(n)。也就是说，如果将包含 n 个结点的单链表构造成跳表，我们需要额外再用接近 n 个结点的存储空间。
在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。
跳表这个动态数据结构，不仅支持查找操作，还支持动态的插入、删除操作，而且插入、删除操作的时间复杂度也是 O(logn)。
作为一种动态数据结构，我们需要某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。
跳表是通过随机函数来维护“平衡性”，当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。
为什么 Redis 要用跳表来实现有序集合，而不是红黑树？
Redis 中的有序集合支持的核心操作主要有下面这几个：
-
插入一个数据；
-
删除一个数据；
-
查找一个数据；
-
按照区间查找数据（比如查找值在 [100, 356] 之间的数据）；
-
迭代输出有序序列。
对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。