关于后端:Redis数据结构六之跳跃表

本文首发于公众号：Hunter 后端
原文链接：Redis 数据结构六之跳跃表

跳跃表构造是有序汇合的底层实现之一，它通过在每个节点中维持多个指向其余节点的指针，从而达到快速访问节点的目标。

当有序汇合蕴含的元素数量较多，又或者有序汇合中的元素的成员是比拟长的字符串时，Redis 就会应用跳跃表来作为有序汇合的底层实现。

以下是本篇笔记目录：

1. 跳跃表及跳跃表节点构造
2. 跳跃表属性
3. 跳跃表节点属性
4. 跳跃表节点层 (level) 的生成
5. 跳跃表的查问过程

1、跳跃表及跳跃表节点构造

接下来介绍一下跳跃表和跳跃表节点构造。

跳跃表构造：

typedef struct zskiplist{
    // 表头节点和表尾节点
    struct skiplistNode *header, *tail;
    
    // 表中节点的数量
    unsigned long length;
    
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

跳跃表构造中蕴含指向表头和表尾的指针，以及 length 字段示意表中节点的数量，level 字段则是示意所有跳跃表节点中最大的节点层数，层数的概念在跳跃表节点构造中再具体阐明。

跳跃表节点构造：

typedef struct zskiplistNode{
    // 后退指针
    struct zskiplistNode *backward;
    
    // 分值
    double score;
    
    // 成员对象
    robj *obj;
    
    // 层
    struct zskiplistLevel {
        // 后退指针
        struct zskiplistNode *forward;
        
        // 跨度
        unsigned int span;
    } level [];} zskiplistNode;

咱们能够将跳跃表了解成链表，不过链表上的每个节点都有指向后面一个节点的指针和多个指向前面某些节点的指针，指向前面的指针以数组的模式存在。

接下来咱们以一张图来示意一下跳跃表及其节点之间的关系。

2、跳跃表构造

在下面的伪代码示例和上图构造中，能够看到一个跳跃表构造如下几个属性：

a) header

header 是跳跃表的头节点指针，能够疾速定位跳跃表的头节点

b) tail

tail 是跳跃表的尾部节点指针，能够疾速定位跳跃表的尾部节点

c) level

level 示意的是跳跃表节点中层数最高的数值，比方在图中第三个跳跃表节点的层数最高，数值是 5，所以跳跃表的这个值是 5。

d) length

length 属性示意的是跳跃表节点的个数，也就是跳跃表的长度。

3、跳跃表节点构造

跳跃表节点的各个属性如下：

a) obj

节点的成员对象，见图中的，o1，o2，o3，是一个指针，指向一个字符串对象，字符串对象保留着一个 SDS 值，就是有序汇合中存储的数值。

b) score

有序汇合用来进行排序的分值，有序汇合通过这个属性用来对汇合的元素进行排序，保留的是 double 类型的浮点数，在跳跃表中，所有节点依照分值从小到大来排序。

c) backward

后退指针，跳跃表的每个节点通过这个属性指向前一个节点，用于从表尾向表头方向拜访节点。

图中展现了如何从表尾向跳跃表的头节点遍历的过程：通过 tail 指针指向跳跃表的尾部节点，而后通过 backward 后退指针一一往前遍历，直到第一个节点的 backward 为 NULL 示意遍历完结。

d) skiplistLevel

skiplistLevel 是跳跃表节点的层，层数介于 1 到 32 之间，每个层的都蕴含两个属性，后退指针和跨度。

后退指针：forward，指向同一层级的下一个跳跃表节点

跨度：span，用于记录到同层级的下一个节点之间的间隔，比方第一个节点的第四层级，下一个节点的第四层级是第三个节点，因而，o1 的第四层级的的跨度是 2。

4、跳跃表节点层 (level) 介绍

后面介绍跳跃表节点的层属性是一个数组，蕴含多个指向下一个同一层级的指针，而每个节点层的大小则是依据幂次定律(power law) 来生成的。

在创立一个跳跃表节点的时候，程序都会依据幂次定律随机生成一个介于 1 到 32 之间的值作为 level 数组的大小，这个规定是越大的数呈现的概率越小，它有一种计算形式，层数每加 1，呈现的概率都是前一个数字的 0.25。

比方 level = 1 的概率是 0.75，那么 level = 2 的概率是 0.75 0.25，level = 3 的概率则是 0.75 0.25 * 0.25，直到最高层数

所以每个跳跃表节点的层数都是随机的，跟这个节点在跳跃表的前后地位无关。

5、跳跃表的查问过程

以下面的图为例，比方咱们想查问 score 为 2.0 的 o2 节点，那么查问的过程是这样的：

1. 首先依据头节点的最高一层节点，在图中是 L5，L5 指向的是 o3 节点，o3 节点的分值比指标分值 2.0 大，舍弃
2. 头节点往降落一层，到 L4，L4 指向下个节点 o1，o1 的 score 比 2.0 小，跳到 o1 节点，持续查问
3. o1 节点的 L4 指向的下一节点是 o3，o3 的 score 比 2.0 大，舍弃，o1 的 L4 持续降落一层
4. o1 节点的 L3 节点指向的 o3 还是不符合条件，持续降落一层
5. o1 节点的 L2 节点指向的 o2 节点，其分值满足条件，而从 o1 到 o2 的跨度为 1 + 1 = 2

如果想获取更多相干文章，可扫码关注浏览：