知一的指纹

Redis数据结构之跳表

跳表(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)。

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

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

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

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

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

跳表在 Redis 中的应用

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

  • 插入一个数据;
  • 删除一个数据;
  • 查找一个数据;
  • 按照区间查找数据;
  • 迭代输出有序序列;

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

关于源码分析:https://segmentfault.com/a/1190000013418471

参考

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

noogel wechat
文章会同步推送到公众号,欢迎关注!
如果此文章能给您带来小小的提升,不妨小额赞赏我一下,以鼓励我写出更好的文章!