youyichannel

志于道，据于德，依于仁，游于艺！

0%

Redis SkipList

发表于 更新于 分类于
本文字数： 3.9k 阅读时长 ≈ 4 分钟

跳表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

Redis 中 Zset 对象的底层实现用到了跳表，跳表支持平均 O(logN)、最坏 O(N) 复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

zset 结构体里有两个数据结构，一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询，也能进行高效单点查询。zset 对象在执行数据插入或是数据更新的过程中，会依次在跳表和哈希表中插入或更新相应的数据，从而保证了跳表和哈希表中记录的信息一致。zset 对象能支持范围查询（如 ZRANGEBYSCORE 操作），这是因为它的数据结构设计采用了跳表，又能以常数复杂度获取元素权重（如 ZSCORE 操作），这是因为它同时采用了哈希表进行索引。

跳表结构设计

跳表是在链表的基础上改进过来的，实现一种「多层」的有序链表，优势是能够快速定位数据。

「跳表结构图」

上图中头节点有 L0, L1, L2 三个指针，分别指向了不同层级的节点，然后每个层级的节点都通过指针连接起来：

  • L0 层级共有 5 个节点：1、2、3、4、5
  • L1 层级共有 3 个节点：2、3、5
  • L2 层级共有 1 个节点：3

现在假设我们要在该结构中查找节点 4 这个元素，只需要查找 2 次就可以定位到节点 4，因为可以在头节点直接从 L2 层级跳到节点 3，然后再跳跃一步找到节点 4；这个过程换作普通的链表需要从头节点开始遍历，需要查找 4 次。

可以看出这个查找过程就是在多个层级上跳跃，最后定位元素，当数据量很大的时候，跳表的查找复杂度就是 O(logN)。

那在 Redis 中，跳表节点是如何实现多层级的呢？

「跳表节点结构」

typedef struct zskiplistNode {
    // zset 对象元素值
    sds ele;
    // 元素权重
    double score;
    // 后向指针，便于从跳表的尾节点开始访问节点，倒序查找
    struct zskiplistNode *backward;
    // 节点 level 数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

跳表是一个带有层级关系的链表，而且每一层级可以包含多个节点，每一个节点通过指针连接起来，实现这一特性就是靠跳表节点结构体中的 zskiplistLevel 结构体类型的 level 数组，level 数组中的每一个元素代表跳表的一层。

注意：跨度和遍历操作没有关系，遍历操作只需要使用到前向指针。

跨度是为了计算节点在跳表中的排位。具体做法：跳表中的节点都是按序排列的，计算某个节点排位时，只需要将从头节点到该节点的查询路径上沿途访问过的所有层的跨度累加起来，得到的结果就是目标节点在跳表中的排位。

比如，查找上图中节点 3 在跳表中的排位，从头节点开始查找节点 3，查找的过程只经过了一个层（L2），并且层的跨度是 3，所以节点 3 在跳表中的排位是 3。

「跳表结构」

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;
  • 跳表的头尾节点，O(1) 时间复杂度内访问跳表的头节点和尾节点；
  • 跳表的长度，O(1) 时间复杂度获取跳表节点的数量；
  • 跳表的最大层数，O(1) 时间复杂度获取跳表中层高最大的那个节点的层数量。

跳表节点的查询过程

查找一个跳表节点时，会从头节点的最高层开始，逐一遍历每一层，在遍历某一层的跳表节点时，会用跳表节点中的 SDS 类型的元素和元素的权重来进行判断，判断条件：

  1. 如果当前节点的权重小于要查找的权重，跳表就会访问该层上的下一个节点；
  2. 如果当前节点的权重等于要查找的权重，并且当前节点的 SDS 类型数据小于要查找的数据时，跳表就会访问该层的上一个节点；
  3. 如果上述两个条件都不满足，或者下一个节点为空时，跳表就会使用目前遍历到的节点的 level 数组里的下一层指针，然后沿着下一层指针继续查找，这就相当于跳到了下一层继续查找。

【🌰栗子】

查找「abcd:4」的节点，查找过程：

  1. 先从头节点的最高层开始，L2 指向「abc:3」节点，这个节点的权重比要查找的节点小，所以要访问该层上的下一个节点；
  2. 由于该层的下一个节点是空节点（level[2] 指向的是 NULL），于是就会跳到「abc:3」节点的下一层继续查找，也就是 level[1]；
  3. 「abc:3」节点的 level[1] 的下一个指针指向了「abcde:4」节点，然后将该节点和要查找的节点进行比较，虽然二者权重相同，但是「abcde:4」节点的 SDS 类型数据大于要查找的数据，于是会继续跳到「abc:3」节点的下一层继续查找，也就是 level[0]；
  4. 「abc:3」节点的 level[0] 的下一个指针指向了「abcde:4」节点，该节点就是要查找的节点，查找结束。

跳表节点层数设置

跳表相邻两层节点数量的比例会影响跳表的查询性能。

跳表相邻两层节点数量最理想的比例是 2:1，这样查找复杂度可以降低到 O(logN)。比如：

如何保持这个比例呢？

首先需要明确，如果采用新增节点或者删除节点时，来调整跳表节点以维持比例的方法的话，会带来额外的开销。

Redis 中采用的是随机数的方式来巧妙解决了这个开销问题，跳表在创建节点时，随机生成每个节点的层数，并没有严格维持相邻两层节点数量的比例为 2:1 的情况。

具体的做法：跳表在创建节点时，会生成一个在 [0,1] 的随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。这样的做法，相当于每增加一层的概率不超过 25%，层数越高，概率越低，层高最大限制是 ZSKIPLIST_MAXLEVEL。

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    static const int threshold = ZSKIPLIST_P*RAND_MAX;
    int level = 1;
    while (random() < threshold)
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

在 Redis 中，层高最大限制是 ZSKIPLIST_MAXLEVEL，那么在创建跳表「头节点」的时候，就会直接创建 ZSKIPLIST_MAXLEVEL 层高的头节点

/* Create a new skiplist. */
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->length = 0;
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    return zsl;
}

ZSKIPLIST_MAXLEVEL 定义的是最高的层数，Redis 7.0 定义为 32，Redis 5.0 定义为 64，Redis 3.0 定义为 32。

为什么使用跳表而不是红黑树

面试题：为什么 Zset 的实现选择跳表而不是平衡树，如 AVL 树、红黑树等？

先来看 Redis 作者的回答：

大致就是考虑内存占用、对范围查找的支持、实现难易程度这三方面的原因。

  1. 并不是内存密集型；
  2. Zset 经常需要执行 ZRANGE 或 ZREVRANGE 的命令，即作为链表遍历跳表。通过此操作，跳表的缓存局部性至少与其他类型的平衡树一样好；
  3. 更易于实现、调试等。

除此之外，

  • 内存占用上，跳表比平衡树更灵活。平衡树每个节点包含 2 个指针，而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。在 Redis里，p=1/4，那么平均每个节点包含 1.33 个指针；
  • 对范围查询的支持上，跳表比平衡树操作更简单。在平衡树上，在找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现；而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。
  • 实现难度上，跳表比平衡树更简单。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速。
相关文章