Redis数据结构—跳跃表 skiplist 实现源码分析

Redis 是一个开源的内存数据结构存储系统,它可以用作数据库、缓存和消息中间件。Redis 的数据结构非常丰富,其中跳跃表(skiplist)是一种重要的数据结构,它被用来实现有序集合(sorted sets)。

跳跃表是一种概率型数据结构,它通过多层链表来实现快速的查找操作。跳跃表的结构类似于多层索引,每一层都是一个有序链表,但每一层的链表节点数量逐渐减少,最顶层的链表节点最少,最底层的链表节点最多。这样设计的好处是,可以在对数时间内完成查找操作,同时插入和删除操作也非常高效。

跳跃表的主要特点包括:

  • 有序性:跳跃表中的元素是有序的,可以快速地进行范围查询。
  • 概率性:跳跃表的高度是随机决定的,这使得它在平均情况下具有对数时间复杂度。
  • 动态性:跳跃表可以在运行时动态地添加和删除元素,而不需要重新构建整个结构。
  • 空间效率:相比于平衡树,跳跃表的空间效率更高,因为它不需要存储指向父节点的指针。

在 Redis 中,跳跃表被用于实现有序集合,它允许用户添加、删除、更新和查询元素,并且可以按照分数对元素进行排序。跳跃表的实现细节在 Redis 源码中可以找到,它是 Redis 高效性的关键因素之一。

以下是根据 Redis 源码对其实现原理的详细分析:

数据结构定义:
Redis 中的跳跃表由 zskiplistNode 和 zskiplist 两个结构体定义。zskiplistNode 表示跳跃表的节点,包含成员对象 obj、分值 score、后退指针 backward 以及层 level 信息;zskiplist 表示跳跃表本身,包含头尾节点指针、长度和层高信息。

节点层级:
跳跃表的每个节点可以有多个层,称为索引层,每个索引层包含一个前向指针 forward 和跨度 span。层高是随机生成的,遵循幂次定律,最大层高为 32。

创建跳跃表:
使用 zslCreate 函数创建一个新的跳跃表,初始化层高为 1,长度为 0,并创建头节点,头节点的层高为 32,其余节点的层高根据需要动态生成。

插入节点:
插入操作首先确定新节点的层高,然后从高层向低层搜索插入位置,并更新 update 数组,该数组记录所有需要调整的前置节点。接着,创建新节点,并根据 update 数组和 rank 数组更新跨度和前向指针。

查找操作:
查找操作从高层开始,沿着链表前进;遇到大于目标值的节点时下降到下一层,继续查找。经过的所有节点的跨度之和即为目标节点的排位(rank)。

删除节点:
删除操作根据分值和对象找到待删除节点,并更新相关节点的前向指针和跨度。如果节点在多层中存在,需要逐层删除。

性能分析:
跳跃表支持平均 O(logN)、最坏 O(N) 复杂度的节点查找,且实现比平衡树简单。在有序集合中,跳跃表可以处理元素数量较多或元素成员较长的情况。

Redis 应用场景:
Redis 使用跳跃表实现有序集合键,特别是当集合中的元素数量较多或元素的成员是较长的字符串时。跳跃表也用于 Redis 集群节点中的内部数据结构。

跳跃表的优点:
跳跃表的优点包括支持快速的查找操作,以及在实现上相对简单。它通过维护多个层级的链表来提高查找效率,且可以顺序性地批量处理节点。

跳跃表的实现细节:
跳跃表的实现细节包括节点的创建、插入、删除、搜索等操作,以及维护跳跃表的最大层高和节点数量等信息。具体实现可以参考 Redis 源码中的 t_zset.c 文件。

Redis 的跳跃表实现是对其有序集合性能和功能的重要支撑,通过上述分析,我们可以更深入地理解这一数据结构的内部机制。

结合 Redis 源码中的跳跃表实现,我们可以深入理解其工作原理。以下是根据 Redis 源码中的跳跃表实现代码进行的分析:

跳跃表节点定义 (zskiplistNode)

typedef struct zskiplistNode {
    robj *obj; // 指向成员对象的指针
    double score; // 分数值
    struct zskiplistNode *backward; // 后退指针,用于从后往前遍历
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned int span; // 跨度,表示该层跨越的元素数量
    } level[]; // 索引层,包含多个索引
} zskiplistNode;

跳跃表定义 (zskiplist)

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头尾节点指针
    unsigned long length; // 跳跃表的长度,即元素数量
    int level; // 跳跃表的最大层数
} zskiplist;

跳跃表的创建 (zslCreate)

zskiplist *zslCreate(void) {
    int j;
    zskiplist *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;
}

跳跃表的插入 (zslInsert)


zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
    // ...
    // 1. 初始化更新数组和 rank 数组
    // 2. 从高层向底层搜索,找到每个层级的插入位置
    // 3. 确定新节点的层数
    // 4. 创建新节点,并更新前向指针和跨度
    // 5. 更新跳跃表的最大层数和长度
    // ...
}

跳跃表的搜索 (zslGetRank)


unsigned long zslGetRank(zskiplist *zsl, double score, robj *o, int reverse) {
    // ...
    // 1. 从高层向底层搜索目标元素
    // 2. 累加跨度以计算元素的排名
    // ...
}

跳跃表的删除 (zslDelete)


zskiplistNode *zslDelete(zskiplist *zsl, double score, robj *obj) {
    // ...
    // 1. 搜索目标元素并记录需要更新的节点
    // 2. 逐层删除节点
    // 3. 更新跨度和前向指针
    // 4. 如果删除了头节点,更新头节点
    // ...
}

跳跃表的高度随机化

Redis 中节点的层高是随机决定的,通常使用固定概率(如 1/2)来确定。但在 Redis 实现中,节点的层高是根据幂次定律随机生成的,介于 1 和 32 之间。

总结

Redis 的跳跃表实现涉及多个关键操作:创建、插入、搜索和删除。每个操作都需要对节点的层级和跨度进行精确管理,以保证跳跃表的有序性和高效的查找性能。跳跃表的高度随机化和层级结构的设计使得 Redis 能够在对数时间内完成查找操作,同时保持了较高的空间效率和动态性。通过源码分析,我们可以更深入地理解 Redis 中跳跃表的内部机制和实现细节。

热门相关:带着仓库到大明   驭房之术   战斗就变强   医门宗师   最强神话帝皇