跳表

发表于 更新于 阅读次数： 本文字数： 2.4k 阅读时长 ≈ 8 分钟

在刚开始工作时，使用到 Redis，在了解其底层数据结构时，接触到了跳表，但是在之后很长时间里，我其实并不了解它。我甚至因为看到跳表的原理图，仍然觉得难以理解，因此对它有点“望而生畏”。直到我读了跳表的代码实现，结合文字说明，我才真正体会到“跳表的实现相比平衡二叉树而言比较简单”这句话是真的。

跳表通过为链表增加多级索引层，使得查找效率从 O(n) 提升到 O(log n)，接近于平衡二叉树的性能，但实现简单且支持高效的动态调整。

跳表具有以下特点：

  • 多级索引：每个节点随机分配一个层级（level），节点的层级越高，出现的概率越低。最高层是全局索引，底层是完整链表。
  • 跳跃查找：通过从上层开始逐级向下查找，快速跳过不需要遍历的节点。
  • 概率性平衡：节点层级由随机算法决定，平均情况下，跳表的性能和层级会保持良好的平衡。

跳表与链表

对我个人而言，跳表是对有序链表的一种优化。

对于有序链表而言，插入、删除、查询等操作的时间复杂度都是 O(n)。随着节点数量增多，性能逐渐变得不能接受。

如何摆脱只能依次遍历节点进行查找的困境呢？跳表在原始链表基础上，建立多级索引，通过多级索引进行查找将增删改查等操作的时间复杂度优化为 O(log n) 。以下是一张典型的跳表示意图：

设定如下：

  • node 层，即原始链表，包含了所有节点
  • level1 索引的节点数量是所有节点数量的 1/2（只是在此处设定的一个概率，在 Redis 中实际为 0.25）
  • 上一层索引的节点数量总是下一层索引节点数量的 1/2

以查找 7 为例：

  1. 从最顶层的索引，即 level2 索引开始查找，发现节点 4 的后继节点为 8，大于 7，因此在节点4向下一层 level1 索引移动
  2. 在 level1 索引依次向前查找，直到节点 6，发现节点 6 的后继节点为 8，大于 7，因此在节点6向下一层 node 层移动
  3. 在 node 层，即原始链表，依次向前查找，查找到节点 7

尽管在此例子中，通过索引查找时移动和比较的次数之和与直接遍历相比相差无几，但是随着节点数量的增大，索引带来的优势显而易见，它能帮助我们快速跳过一个范围的节点，这就是所谓的“跳跃查找”

然而，个人认为对于刚刚接触跳表的人而言，上面的原理示意图并不能很好的体现出具体实现中的数据结构，以致于会带来一些困惑。

  • 没有向前的指针，如何从顶层索引开始查找到节点 3？
  • 跳表的节点分布形状看起来和二叉树很像，如何构造它，会不会像构造平衡二叉树一样麻烦？

跳表节点的结构

下图是一张拥有更多细节的跳表示意图。

跳表节点的代码如下，其中 Node 除了包含 value 外，还拥有当前节点的层级 level 和一个向前指针数组 forwards，数组大小等于 level，其中每个元素分别指向相应层级的后继节点。

1
2
3
4
5
public class Node {
    private int value;
    private int level;
    private final Node[] forwards;
}

在 Redis 中，节点还包含向后的指针 backwards 用于优化逆序查找。

对我个人而言，结合上图和代码之后，跳表变得更容易理解了。

  • 每个位置实际上只有一个数据节点 Node，内部包含多层索引
  • 多层索引通过一个 Node 数组实现
    • forwards[i] 代表在第 i 层
    • 在第 i 层向前移动就是 cur = cur.forwards[i]
    • 从第 i 层向下移动到第 i-1 层，就是 cur.forwards[i] 变为 cur.forwards[i-1]
  • 使用一个头节点，其多层索引指向每一层的第一个节点

在代码中，我们会看到向前和向下的移动的实现是比较巧妙的。

增删改查等操作

查找

查找目标节点的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public Node get(int value) {
    // 从头节点开始
    Node cur = head;
    // 从最顶层开始查找
    for (int i = level - 1; i >= 0; i--) {
        // 遍历当前层，找到小于目标值的最大值所在的节点
        while (cur.forwards[i] != null && cur.forwards[i].value < value) {
            cur = cur.forwards[i];
        }
        // 判断后继节点是否为目标
        // 如果不是，下一次循环时 i--，代表指针向下层移动
        if (cur.forwards[i] != null && cur.forwards[i].value == value) {
            return cur.forwards[i];
        }
    }
    return null;
}

和原理相比，实现越简单，越让人感觉巧妙啊。

添加

构造跳表的过程，也就是依次添加节点的过程。主要需要处理几个问题：

  1. 如何生成节点的索引层级
  2. 查找和记录在每一层需要插入节点的位置
  3. 插入节点
  4. 更新跳表的层级

添加节点的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public void add(int value) {
    // 随机生成节点的索引层级
    int level = randomLevel();
    // 创建新节点
    Node newNode = new Node();
    newNode.value = value;
    newNode.level = level;
    // updates 用于记录每一层需要插入新节点的位置，初始化为头节点
    Node[] updates = new Node[level];
    for (int i = level - 1; i >= 0; i--) {
        updates[i] = head;
    }
    // 查找每一层需要插入新节点的位置
    Node cur = head;
    for (int i = level - 1; i >= 0; i--) {
        while (cur.forwards[i] != null && cur.forwards[i].value < value) {
            cur = cur.forwards[i];
        }
        updates[i] = cur;
    }
    // 插入节点
    for (int i = level - 1; i >= 0; i--) {
        newNode.forwards[i] =  updates[i].forwards[i];
        updates[i].forwards[i] = newNode;
    }
    // 如果跳表当前的层级小于新节点的索引层级，则更新
    if (this.level < level) {
        this.level = level;
    }
}

注意：在查找时可以通过判断提前返回，在添加时不可以。

随机生成节点的层级的代码如下：

1
2
3
4
5
6
7
private int randomLevel() {
    int level = 1;
    while (Math.random() > PROBABILITY && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

在 Redis 中，随机生成节点的层级的代码如下：

1
2
3
4
5
6
int zslRandomLevel(void) {
    int level = 1;
    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

假设我们期望当前层的节点数量是下一层的节点数量的一半，概率就是 0.5。在 Redis 中，ZSKIPLIST_P = 0.25。
假设我们期望顶层索引的数量为 2，最大节点数量为 1024，最大高度就是 10。在 Redis 中，ZSKIPLIST_MAXLEVEL = 32，最大节点数量估计大部分情况下受限于内存容量。

节点层级由随机算法决定，平均情况下，跳表的性能和层级会保持良好的平衡，这被称为概率性平衡。

删除

删除节点的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void delete(int value) {
    // 定位待删除节点的位置
    Node cur = head;
    Node[] updates = new Node[level];
    for (int i = level - 1; i >= 0; i--) {
        while (cur.forwards[i] != null && cur.forwards[i].value < value) {
            cur = cur.forwards[i];
        }
        updates[i] = cur;
    }
    // 检查目标节点是否存在
    if (cur.forwards[0] != null && cur.forwards[0].value == value) {
        for (int i = level - 1; i >= 0; i--) {
            if (updates[i].forwards[i] != null && updates[i].forwards[i].value == value) {
                updates[i].forwards[i] = updates[i].forwards[i].forwards[i];
            }
        }
    }
    // 如果删除的目标节点是唯一最高节层，则减少层级
    while (level > 1 && head.forwards[level - 1] == null) {
        level--;
    }
}

在 Redis 中，删除节点时，还需要处理向后的指针，相关代码见下方：

1
2
3
4
5
if (x->level[0].forward) {
    x->level[0].forward->backward = x->backward;
} else {
    zsl->tail = x->backward;
}

其中 x 是待删除节点。

更新

跳表既可以允许重复值，也可以不允许重复值。

在 Redis 中，zset 将 double 类型的 score 和 sds 类型的 ele 作为整体对象进行处理，允许不同 ele 拥有相同的 score，也允许修改 ele 的 score。
根据注释，zslInsert 方法由调用者保证 ele 不存在，调用者通过 hash table 测试 ele 是否存在；
修改分数的操作实际上是通过“删除旧节点 + 插入新节点”实现，以确保跳表的有序性和高效查找能力。这种实现方法简单、清晰，同时能够在保证性能的前提下完成节点的修改。

对于不同 ele 拥有相同的 score，应对的相关代码见下方：

1
2
3
4
5
6
7
8
9
10
11
12
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
    while (x->level[i].forward &&
            (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                    // 应对同 score 但不同 ele 的情况
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
    {
        x = x->level[i].forward;
    }
    update[i] = x;
}

更多细节见 Redis 的源代码 src/t_zset.c。

补充

在 Redis 中，zset 有两种不同的实现，分别是 ziplist 和 skiplist。

使用命令 object encoding key 可以查看目标的底层数据结构

  • 当同时满足以下两个条件时，使用 ziplist：
    • 保存的键值对数量少于 128 个，zset-max-ziplist-entries 128
    • 每个元素的大小小于 64 字节，zset-max-ziplist-value 64
  • 如果不同时满足上述两个条件，那么使用 skiplist

考虑到内存空间的稀缺性，在满足条件的情况下使用 ziplist 既可以节约内存，又可以保证效率。这不禁让人想到，在计算机底层，很多时候处理的就是连续的小块对象，为的就是平衡效率和空间。