My-Notes

Search

SearchSearch

019.跳表

Sep 02, 2024, 7 min read

Redis 只有 Zset 对象的底层实现用到了跳表，跳表的优势是能支持平均 O(logN) 复杂度的节点查找

Zset 结构体中有两个数据结构：一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询，也能进行高效单点查询

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

Zset 在执行增删改时，会依次在跳表和哈希表中进行修改，从而保证跳表和哈希表中记录的信息一致

跳表结构设计

链表在查找元素时，需要逐一查找，时间复杂度是 O(N)。跳表是在链表基础上改进的，实现了一种「多层」的有序链表，能够快速定位数据

// 跳表节点
typedef struct zskiplistNode {
    sds ele; // 元素值
    double score; // 分值（权重值）
    struct zskiplistNode *backward; // 后向指针（指向前一个节点）
  
    // 「多层」数组
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前向指针（指向后一个节点）
        unsigned long span; // 跨度
    } level[];
} zskiplistNode;
  • 后向指针：指向前一个节点，目的是方便倒序查找
  • level 数组：实现「多层」的有序链表
    • 前向指针：指向后一个节点
    • 跨度：记录两个节点之间的距离

遍历操作只需要用前向指针就可以完成，与跨度无关

跨度实际上是为了计算节点在跳表中的排位，排位（Rank）是指从跳表的头节点到目标节点之间跨越的节点总数，即该节点在有序集合中的位置索引。通过累加每一层的 span，可以快速计算出当前节点的排位

图中的头节点也是 zskiplistNode 跳表节点，只不过后向指针、权重、元素值都没有用到，所以图中省略了这部分

// 跳表
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头尾节点
    unsigned long length; // 跳表长度
    int level; // 跳表最大层数
} zskiplist;

跳表节点查询过程

从头节点的最高层开始，比较当前层下一个节点和要查找的元素：

  • 下一个节点为空
  • 下一个节点的权重「大于」要查找元素的权重
  • 下一个节点的权重「等于」要查找元素的权重，但下一个节点的 SDS 类型的元素值字典序「大于」要查找元素

上述条件只要有一个成立，就会跳到下一层，否则跳到当前层的下一个元素

即：从头节点的最高层开始向右比较，比较成功就向右跳，比较失败就向下跳

跳表节点层数设置

跳表相邻两层的节点数量比例会影响跳表的查询性能，最理想的比例是 2:1，查找复杂度可以降低到 O(logN)

怎样维持相邻两层节点数量的比例为 2:1？

如果在增删节点时，来调整跳表节点以维持比例的话，会带来额外的开销

Redis 采用一种随机的方法（创建节点时随机生成层数），并没有严格维持相邻两层的节点数量比例为 2:1

具体的做法是，跳表在创建节点时，生成一个范围 [0-1) 的随机数，如果小于 0.25，那么层数增加 1 层，然后继续生成下一个随机数，直到大于 0.25

相当于每增加一层的概率不超过 25%，层数越高，概率越低，层高最大限制是 32。在创建跳表「头节点」时，会直接创建 32 层高的头节点

层高最大限制：Redis 3.0 定义为 32，Redis 5.0 定义为 64，Redis 7.0 定义为 32

为什么用跳表而不用平衡树？

一个常见的面试题：为什么 Zset 的实现用跳表而不用平衡树（如 AVL 树、红黑树等）？

  • 内存占用上，跳表比平衡树更灵活：
    • 平衡树每个节点包含 2 个指针（分别指向左右子树）
    • 跳表每个节点包含的指针数目平均为 1/(1-p)，Redis 的实现取 p = 0.25，平均每个节点包含 1.33 个指针，比平衡树更有优势
  • 范围查找时，跳表比平衡树操作要简单：
    • 在平衡树上，找到指定范围的小值之后，还需要以中序遍历继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现
    • 而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以
  • 实现难度上，跳表比平衡树简单得多：
    • 平衡树的插入和删除操作可能引发子树的调整，逻辑复杂
    • 而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速

Graph View

Backlinks