Redis源码剖析与实战
蒋德钧
中科院计算所副研究员
新⼈⾸单¥59.9
2185 人已学习
课程目录
已更新 9 讲 / 共 33 讲
0/4登录后,你可以任选4讲全文学习。
课前导读 (2讲)
开篇词 | 阅读Redis源码能给你带来什么?
免费
01 | 带你快速攻略Redis源码的整体架构
数据结构模块 (6讲)
02 | 键值对中字符串的实现,用char*还是结构体?
03 | 如何实现一个性能优异的Hash表?
04 | 内存友好的数据结构该如何细化设计?
05 | 有序集合为何能同时支持点查询和范围查询?
06 | 从ziplist到quicklist,再到listpack的启发
07 | 为什么Stream使用了Radix Tree?
事件驱动框架和执行模型模块 (1讲)
08 | Redis server启动后会做哪些操作?
Redis源码剖析与实战
15
15
1.0x
00:00/00:00
登录|注册

07 | 为什么Stream使用了Radix Tree?

你好,我是蒋德钧。这节课,我们继续从底层数据结构的视角出发,来聊聊 Redis 中的 Stream 数据类型是如何保存消息的。
Redis 从 5.0 版本开始支持提供 Stream 数据类型,它可以用来保存消息数据,进而能帮助我们实现一个带有消息读写基本功能的消息队列,并用于日常的分布式程序通信当中。我在讲如何使用 Redis 实现消息队列的时候,曾介绍过 Stream。当时,有不少同学就说想学习了解下 Stream 的实现,以便掌握 Stream 内部结构的操作特点,但自己对 Stream 类型不太熟悉,不知道 Stream 底层是采用怎样的数据结构来保存消息数据的。
其实,为了节省内存空间,在 Stream 数据类型的底层数据结构中,采用了 Radix Tree 和 listpack 两种数据结构来保存消息。我在第 6 讲已经给你介绍过了 listpack,它是一个紧凑型列表,在保存数据时会非常节省内存。
所以今天这节课,我就来给你介绍下 Stream 用到的另一个数据结构 Radix Tree。这个数据结构的最大特点是适合保存具有相同前缀的数据,从而实现节省内存空间的目标,以及支持范围查询。
同时,和常见的 B 树或 B+ 树类似,Radix Tree 也是一种重要的树型结构,在操作系统内核和数据库中也有应用。所以,了解 Radix Tree 的设计与实现,既可以帮助我们掌握 Stream 的实现思路,还可以让我们把 Radix Tree 应用到需要节省内存的有序树型索引场景中,进一步解决具有公共前缀的大量数据保存时的内存开销问题。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/1000字
划线
笔记
复制
该试读文章来自付费专栏《Redis源码剖析与实战》,如需阅读全部文章,
请订阅文章所属专栏新⼈⾸单¥59.9
立即订阅
登录 后留言

精选留言(4)

  • Kaito
    作为有序索引,Radix Tree 也能提供范围查询,和我们日常使用的 B+ 树,以及第5讲中介绍的跳表相比,你觉得 Radix Tree 有什么优势和不足么?

    1、Radix Tree 优势

    - 本质上是前缀树,所以存储有「公共前缀」的数据时,比 B+ 树、跳表节省内存
    - 没有公共前缀的数据项,压缩存储,value 用 listpack 存储,也可以节省内存
    - 查询复杂度是 O(K),只与「目标长度」有关,与总数据量无关
    - 这种数据结构也经常用在搜索引擎提示、文字自动补全等场景

    Stream 在存消息时,推荐使用默认自动生成的「时间戳+序号」作为消息 ID,不建议自己指定消息 ID,这样才能发挥 Radix Tree 公共前缀的优势。

    2、Radix Tree 不足

    - 如果数据集公共前缀较少,会导致内存占用多
    - 增删节点需要处理其它节点的「分裂、合并」,跳表只需调整前后指针即可
    - B+ 树、跳表范围查询友好,直接遍历链表即可,Radix Tree 需遍历树结构
    - 实现难度高比 B+ 树、跳表复杂

    每种数据结构都是在面对不同问题场景下,才被设计出来的,结合各自场景中的数据特点,使用优势最大的数据结构才是正解。
    2021-08-10
    5
  • 曾轼麟
    在阅读的时候其实已经有想到Radix Tree,B+树 和跳表之间的区别,没想到老师文章最后刚好提到这个问题,那我就站在我个人理解的角度回到一下我的想法,问题是:【Radix Tree,B+ 和跳跃表之间的区别】

    【我分为以下几个问题自问自答带出我的想法和思考的角度】

    问题一:B+树和跳跃表有什么关联?
    答:
    1、B+树和跳跃表这两种数据结构在本身设计上是有亲缘关系的,其实如果把B+树拉直来看不难发现其结构和跳跃表很相似,甚至B+树的父亲结点其实类似跳跃表的level层级。
    2、在当前计算机硬件存储设计上,B+树能比跳表存储更大量级的数据,因为跳表需要通过增加层高来提高索引效率,而B+树只需要增加树的深度。此外B+树同一叶子的连续性更加符合当代计算机的存储结构。然而跳表的层高具有随机性,当层高较大的时候磁盘插入会带来一定的开销,且不利于分块。

    问题二:那么为什么Redis不使用B+树呢而选择跳表呢?
    答:因为数据有序性的实现B+树不如跳表,跳表的时间性能是优于B+树的(B+树不是二叉树,二分的效率是比较高的)。此外跳表最低层就是一条链表,对于需要实现范围查询的功能是比较有利的,而且Redis是基于内存设计的,无需考虑海量数据的场景。

    问题三:Radix Tree优势在哪?
    答:
    1、当存储大量key字符串很长的时候跳表不如前缀树,甚至不利于实现这种场景,因为跳表层高有最大限制,此外跳表不能很好的标识key的字符串顺序,不像前缀树可以从根目录下路就是字符顺序。
    2、在内存环境下,前缀树是二叉树,而B+树不是,这样一来当对于key的索引效果来说,前缀树会比B+树索引效果更好(类比:新华字典目录越丰富,通过目录快速定位到目标字的概率更高)。

    问题四:Radix Tree劣势在哪?
    答:
    1、Radix Tree能保证在索引key的前缀顺序,但是在保证数据顺序且连续性上不如跳表。
    2、查询性能上存在欠缺,虽然是二叉树但是当访问一个key的时候每次都需要依次访问前缀字符,不如hash表对整个key的直接索引。
    3、不适合存储像UUID等,非对称结构的key(而且使用时候建议让Redis自动生成)。
    2021-08-11
  • 可怜大灰狼
    最后一个图有点懵。listpack那里不应该画listpack内存结构么?然后listpack的master entry放key,后面的entry放value。我怎么感觉又是一个raxNode。
    2021-08-10
  • Ethan New
    这个课的内容之前不太了解,得多看几遍才能理解,我太菜了。。。
    2021-08-10
收起评论
4
返回
顶部