【redis】前缀树 trie-radix tree-rax

前缀树（trie），基数树（radix tree），redis 自适应基数树（rax tree），都是 前缀压缩树（prefix tree）的变种 ，在存储效率、查询性能、功能逐步优化。

一 trie

1.1 特点

存储方式：每个节点存单个字符，路径组成完整的键。
查询复杂度：O(k)，k 是键的长度。
空间浪费：存在大量单分支节点。

示例：
存储键 ["apple", "app", "banana"]：

        (root)
       /     \
      a       b
     /         \
    p           a
   / \           \
  p   p           n
 /     \           \
l       l           a
e       e           n
                     a

问题："app" 和 "apple" 共享 "app" 前缀，但 "p" 节点仍然分叉，导致冗余。

二 radix tree

基数树，也叫压缩前缀树

改进点：

• 合并单分支路径：把连续的单节点，合并为一个节点。存字符串片段，而不是单个字符。
• 空间优化：减少节点数量。

示例：
存储相同的键 ["apple", "app", "banana"]：

        (root)
       /     \
     app     banana
    /   \
   le    (empty)

优化："app" 和 "apple" 共享 "app" 节点，"le" 作为子节点挂载。

场景：适合有 较长公共前缀 的场景。如 url 路由。

三 rax tree (redis adaptive radix tree)

改进点：

1. 自适应节点类型：
   - 根据子节点数量，动态选择 4 种节点类型：
   - ​单字符节点​（传统 Trie 节点）。
   - ​多字符节点​（压缩路径）。
   - ​数组节点​（子节点较多时用数组存储）。
   - ​哈希节点​（子节点非常多时转为哈希表）。
   - 平衡 ​查询速度 和 ​内存占用。
2. 高效范围查询：
   - 因为 键 有序，如 stream 的 timestamp-sequence 的 id，支持 xrange 等操作。范围查询 O(log n), 点查 O(k)
3. 内存压缩：
   - 通过 惰性删除 和 节点合并 减少碎片。

应用：消息 id （如 1630000000000-1）作为键，内容存储在叶子节点。

3.1 自适应节点类型

Redis 的 RAX Tree（自适应基数树） 通过动态选择 4 种节点类型 来优化内存和查询效率。这种设计是它的核心创新之 一，下面详细解释其工作原理和兼容性。
• RAX Tree 的自适应性 使其在 不同数据分布下均高效，而无需手动选择数据结构。
• Redis Stream 受益于此：消息 ID 的有序性和前缀压缩特性与 RAX Tree 完美匹配。
• 其他系统（如 ART） 也采用类似设计，但 RAX 更注重工程实现（如惰性转换）。

3.1.1 节点类型

RAX Tree 根据 子节点的数量 动态选择节点类型，以平衡 查询速度 和 内存占用：

单字符节点（Single-Char Node）

• 适用场景：子节点数量 ≤ 1（路径尚未压缩）。
• 结构：
• 类似传统 Trie 节点，每个节点存储 1 个字符。
• 子节点通过指针链接。
• 示例：

(root) → 'a' → 'p' → 'p' → 'l' → 'e'

• 缺点：内存浪费（长路径需要多个节点）。

多字符节点（Multi-Char Node）

• 适用场景：子节点数量 = 1，但路径可压缩。
• 结构：
• 存储 连续的字符串片段（如 "app"），而非单个字符。
• 子节点直接挂载到片段末尾。
• 示例：

(root) → "app" → "le"  // 存储 "apple"

• 优化点：减少节点数量，提升内存效率。

数组节点（Array Node）

• 适用场景：子节点数量 ≤ 16（经验值）。
• 结构：
• 使用 固定大小的数组（如 children[16]）存储子节点。
• 数组索引对应字符的 ASCII 码（如 'a' 对应 children[97]）。
• 优势：
• 查询速度 O(1)（直接通过数组下标访问）。
• 适合中等规模子节点。

哈希节点（Hash Node）

• 适用场景：子节点数量 > 16（避免数组稀疏浪费）。
• 结构：
• 使用 哈希表（如 dict）存储子节点。
• 键是字符（或字符串片段），值是对应的子节点指针。
• 优势：
• 内存高效（仅存储存在的子节点）。
• 查询速度 接近 O(1)（哈希表平均复杂度）。

3.1.2 特点

动态切换节点类型

RAX Tree 在运行时 根据子节点数量自动升级/降级节点类型，例如：

1. 插入时：
   • 初始为 单字符节点（如插入 "a"）。
   • 继续插入 "b" 时，子节点数=2 → 转换为 数组节点。
   • 若子节点数超过 16 → 转换为 哈希节点。
2. 删除时：
   • 哈希节点子节点数 ≤ 16 → 降级为 数组节点。
   • 数组节点子节点数=1 → 降级为 多字符节点 或 单字符节点。

统一接口

所有节点类型对外提供一致的 CRUD 操作接口（如 raxInsert, raxFind），内部处理差异对用户透明。

惰性转换

• 节点类型不会频繁切换，仅在 子节点数显著变化时 触发转换。
• 转换成本由 Redis 后台任务分摊，避免阻塞主线程。

内存与性能平衡

• 单字符/多字符节点：节省内存，适合稀疏数据。
• 数组节点：快速查询，适合中等密度数据。
• 哈希节点：支持高密度数据，避免数组浪费。

3.1.3 实际应用示例（Redis Stream）

假设 Stream 消息 ID 为 "1630000000000-1"：

1. 插入过程：
   • 初始为单字符节点（'1'）。
   • 插入 '6'、'3'… 后，合并为多字符节点（如 "163"）。
   • 后续字符较多时，可能转为数组节点或哈希节点。
2. 查询过程：
   • 直接按路径查找（如 "163" → "0000000000" → "-1"）。
   • 范围查询（XRANGE）利用有序特性遍历叶子节点。

四 其他