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
0.75x
1.0x
1.25x
1.5x
2.0x
登录
|
注册
07 | 为什么Stream使用了Radix Tree?
蒋德钧
2021-08-10
你好,我是蒋德钧。这节课,我们继续从底层数据结构的视角出发,来聊聊 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
下载
客户端
返回
顶部