RadixTree优劣
RadixTree优势
- 本质上是前缀树,所以存储有「公共前缀」的数据时,比 B+ 树、跳表节省内存
- 没有公共前缀的数据项,压缩存储,value 用 listpack 存储,也可以节省内存
- 查询复杂度是 O(K),只与「目标长度」有关,与总数据量无关
- 这种数据结构也经常用在搜索引擎提示、文字自动补全等场景
RadixTree不足
- 如果数据集公共前缀较少,会导致内存占用多
- 增删节点需要处理其它节点的「分裂、合并」,跳表只需调整前后指针即可
- B+ 树、跳表范围查询友好,直接遍历链表即可,Radix Tree 需遍历树结构
- 实现难度高比 B+ 树、跳表复杂
Redis中 Stream 在存消息时,推荐使用默认自动生成的「时间戳+序号」作为消息 ID,不建议自己指定消息 ID,这样才能发挥 Radix Tree 公共前缀的优势。
每种数据结构都是在面对不同问题场景下,才被设计出来的,结合各自场景中的数据特点,使用优势最大的数据结构才是正解。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 月怿姝雪颜!
评论
Disquslivere