Redis源码学习之跳表

  • 跳跃链表

跳跃链表简称为跳表(SkipList),它维护了一个多层级的链表,且第i+1层链表中的节点是第i层链表中的节点的子集。跳表作为一种平衡数据结构,经常和平衡树进行比较,在大多数场景下,跳表都可以达到平衡树的效率(查询节点支持平均O(lgN),最坏O(N)的复杂度),但实现和维护起来却比平衡树简单很多。(跳跃列表由 William Pugh 发明。他在 Communications of the ACM发表了《Skip lists: a probabilistic alternative to balanced trees》,在其中详细描述了他的工作)

  • 跳表在Redis中的使用
  1. 有序集合对象(SortedSet)底层实现之一
  2. 集群节点内部数据结构
  • 跳表在Redis中的实现
  1. 数据结构 跳表节点,包含了节点中存储的数据obj和对应的分值score,以及每个节点的层数结构,每层都包含着前进指针与跨度;除此之外,每个节点还包含一个后退指针,假设跳表只有一层,那么整个跳表将退化为双端链表。

这里需要明确一下跨度的定义:从前驱节点到自身经历的节点数(包含前驱节点在内),如下图连接线上数字即为箭头指向节点的在对应层的跨度。

跳表,持有跳表的结构包括指向跳表表头和表尾的指针,以及整个跳表的长度(即第一层的节点数,但不包含头结点),还有整个跳表最高层的层数。这里需要指出的是,表头节点是一个包含了所有层的虚拟节点(不包含任何数据),每一层中表头节点的forward都指向该层的第一个真实节点。

最终,Redis中的一个长度为2,层高为2的跳表如下图所示

  1. 插入节点 当进行插入操作的时候,程序会维护两个数组,rank数组保存每层中插入节点前驱前驱节点的排行值,update数组保存每层插入节点的前驱节点,以下图为例:

在一个长度为4,高度为5的跳表中插入score为20,值为字符串c的节点,首先由上至下遍历每层查找插入位置,同时维护每层的rank值和update节点,遍历完之后,rank和update数组如图中所示,我们将其中的4层(即i=3)拿出来分析一下。在插入节点之前,update[3]指向头结点,rank[3]=0,rank[0]=2,第三层左边节点到右边节点的跨度是4,那么从图中可以看出,新节点的跨度=左边节点(即插入节点的前驱)跨度-(rank[0]-rank[3]),这里的rank[0]-rank[3]可以进一步模型化为rank[0]-rank[i],从上文中可以看出来,实际上rank[0]-rank[i]就表示,插入节点与插入节点前驱节点之间的节点数(不包含前驱节点自身),所以在原跨度中将其减掉,就是插入节点的跨度了。

当节点插入后,如下图所示。可以通过图中公式计算出插入节点的前驱节点的跨度。

整个例子走下来之后,我们可以通过流程图来回顾一下:

代码如下:

  1. 删除节点(内部函数) 删除节点被多个public方法调用,用于删除某个分值为score,对象为obj的节点。需要外部方法遍历节点各层后,维护update数组作为输入,需要注意这里跨度值的维护,代码实现如下:
  1. 删除节点(公开方法) 此方法对外公开,首先从上至下遍历各层维护好update数组,再调用内部删除节点方法,代码实现如下:
  1. 获取指定节点在跳表中的排行值 有了插入代码中排行值的讲解,相信你自己也可以实现这部分代码了,只需要在遍历的同时将跨度进行累加即可,代码实现如下:
  • 综述 上文中笔者只列出了自认为比较核心的方法,通过这几个方法也基本可以了解Redis中跳表的实现思想,总的来说与常规实现方法差别不大,只是对于排行值的需求定义并维护了每个节点的跨度。另外,值得一提的是,Redis中跳表的最高层数为32,层数越高出现的概率越低。在后面对于有序集合对象的介绍中,还会再次涉及到跳表。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

详解斯坦纳点及斯坦纳树及模版归纳总结

①什么是斯坦纳点?   假设原来已经给定了个点,库朗等指出需要引进的点数至多为,此种点称为斯坦纳点。过每一斯坦纳点,至多有三条边通过。若为三条边,则它们两两交成...

93760
来自专栏ACM算法日常

年会Party(树形动态规划)- HDU 1520

There is going to be a party to celebrate the 80-th Anniversary of the Ural Stat...

9520
来自专栏数据结构与算法

P1008 三连击

题目背景 本题为提交答案题,您可以写程序或手算在本机上算出答案后,直接提交答案文本,也可提交答案生成程序。 题目描述 将1,2,…,9共9个数分成三组,分别组成...

43690
来自专栏程序生活

美团NLP实习面试总结一 基本知识4 数据结构二 NLP相关技术1 LSTM2 介绍实体链接与实体映射3 解释随机游走的原理及作用4 命名实体识别

机会总是留给有准备的人 一 基本知识 1 python 解释下装饰器和生成器的作用以及用法 类的知识点,类与对象,三个输出 2 java HashMap的实现原...

46630
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (中)

上一部分提到了节点(Node),代价(Cost),估价公式等基本概念,有了这些知识铺垫 就可以正式开启寻路之旅了! ? 如上图,这是一个5行8列的网格,黄色节点...

27560
来自专栏云霄雨霁

字符串查找----查找算法的选择

31100
来自专栏数据结构与算法

cf1027F. Session in BSU(并查集 匈牙利)

$n$个人,每个人可以在第$a_i$天或第$b_i$,一天最多考一场试,问在最优的情况下,最晚什么时候结束

13610
来自专栏Java3y

Map集合、散列表、红黑树介绍

21530
来自专栏蘑菇先生的技术笔记

探索c#之跳跃表(SkipList)

29580
来自专栏hanlp学习笔记

hanlp中的N最短路径分词

N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法,张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。该算法...

17300

扫码关注云+社区

领取腾讯云代金券