B+树和跳跃表有什么关联？

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

为什么Redis不使用B+树呢而选择跳表呢？

  • 因为数据有序性的实现B+树不如跳表，跳表的时间性能是优于B+树的（B+树不是二叉树，二分的效率是比较高的）。此外跳表最低层就是一条链表，对于需要实现范围查询的功能是比较有利的，而且Redis是基于内存设计的，无需考虑海量数据的场景。

Radix Tree优势在哪？

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

Radix Tree劣势在哪？

  • 如果数据集公共前缀较少，会导致内存占用多
  • 增删节点需要处理其它节点的「分裂、合并」，跳表只需调整前后指针即可
  • B+ 树、跳表范围查询友好，直接遍历链表即可，Radix Tree 需遍历树结构
  • 实现难度高比 B+ 树、跳表复杂
  • 不适合存储像UUID等，非对称结构的key（而且使用时候建议让Redis自动生成）