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

精选留言(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

  

  