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

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
简介: Redis 是一个内存中的数据结构服务器,使用跳跃表(skiplist)来实现有序集合。跳跃表是一种概率型数据结构,支持平均 O(logN) 查找复杂度,它通过多层链表加速查找,同时保持有序性。节点高度随机生成,最大为 32 层,以平衡查找速度和空间效率。跳跃表在 Redis 中用于插入、删除和按范围查询元素,其内部节点包含对象、分值、后退指针和多个前向指针。Redis 源码中的 `t_zset.c` 文件包含了跳跃表的具体实现细节。

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 中跳跃表的内部机制和实现细节。

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
18天前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
23天前
|
存储 消息中间件 NoSQL
Redis 数据结构与对象
【10月更文挑战第15天】在实际应用中,需要根据具体的业务需求和数据特点来选择合适的数据结构,并合理地设计数据模型,以充分发挥 Redis 的优势。
54 8
|
22天前
|
存储 NoSQL Java
介绍下Redis 的基础数据结构
本文介绍了Redis的基础数据结构,包括动态字符串(SDS)、链表和字典。SDS是Redis自实现的动态字符串,避免了C语言字符串的不足;链表实现了双向链表,提供了高效的操作;字典则类似于Java的HashMap,采用数组加链表的方式存储数据,并支持渐进式rehash,确保高并发下的性能。
介绍下Redis 的基础数据结构
|
18天前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
18天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
5天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
15 1
|
8天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
11天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
13天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
40 4