Redis数据结构之跳表

发表于 2019-07-25

跳表（Skip List）

怎样理解跳表

用一种比较通俗的方式去说，跳表是一种带有 N 级索引的有序链表，其中 N 级索引的作用是可以加速查找到链表的目标节点。

比较大众化的解释是，跳表是一个随机化的数据结构，实质就是一种可以进行『二分』查找的有序链表。这里对于随机化的理解是 N 级索引节点的选择上。

跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。在一定程度上可以代替红黑树（Red-black tree）。

从链表说起，对于普通链表中，即使其存储的数据是有序的，当我们要寻找一个数据，时间复杂度也会比较高 O(n)。

然后我们对链表建立一级索引，每两个节点提取一个节点放到索引层，其中的 down 指针指向下一级。

当我们寻找节点 16，只需要走过 1' -> 4' -> 7' -> 9' -> 13' -> 13 -> 16 节点即可（17'也要访问判断），而原始链表需要走过 10 个节点，节省了 2 个节点路径。如果我们再抽出二级索引后是这样子的。

寻找节点 16 只需要走过 1'' -> 7'' -> 13'' -> 13' -> 13 -> 16 节点。这样我们又可以加快查找到目标节点，图中举例节点比较靠前，试想节点靠后，并且增加了 N 级索引之后效率一定会提升很多。

单一链表的查询时间复杂度是 O(n)，插入、删除的时间复杂度也是 O(n)。

以两个节点为跨度的话，那么跳表有如下总结：

第 k 级索引的节点个数是 n/(2^k)
假设有 h 级索引，最高级索引有 2 个节点，高度 h=log2n - 1 (2为底数)，每一层都遍历 m 个节点，时间复杂度为 O(m*log n)。此时算得 m=3。

以多个节点为跨度，可以节省更多节点，是空间和时间上的相互折中。在实际开发中，索引节点只存储关键值和关键指针，之后链表节点才存储实际对象。

跳表的的查询、插入、更新、删除时间复杂度均为 O(log n)。

如何选择索引层？通过一个随机函数决定将节点插入到哪几级索引中，随机函数特点是要保证跳表索引大小和数据大小平衡性。

Redis 中有序集合通过散列表 + 跳表实现的，主要支持的功能有：

相比红黑树，跳表在区间查找上有更好的性能；并且实现起来也相对容易；可以通过调整索引策略来平衡性能和内存使用；红黑树插入删除时为了平衡高度需要旋转附近节点，高并发时需要锁，跳表不需要考虑。

https://www.jianshu.com/p/dd01e8dc4d1f
https://blog.csdn.net/pcwl1206/article/details/83512600