一、Radix树是什么？

Radix树又叫「基数树」或「压缩前缀树」，本质是一种优化版的「字典树（Trie）」。

类比理解：
如果把Trie树比作「按字母顺序排列的词典」（每个字母单独占一层节点），那么Radix树就是「压缩版词典」—— 把连续相同的前缀「合并成一个节点」，就像把词典里以“app”开头的单词（如apple、app、appreciate）的前缀合并成一个“app”节点，后面直接接不同的后缀。

二、Radix树的核心特点：压缩前缀，减少节点

普通Trie树 vs Radix树对比： （以单词“app”、“apple”、“ape”为例）

- Trie树结构：
  root
  ├─ a
  │ ├─ p
  │ │ ├─ p
  │ │ │ └─ (结束，代表app)
  │ │ └─ l
  │ │   ├─ e (结束，代表apple)
  │ └─  e (结束，代表ape)
- Radix树结构：
  root
  └─ app  # 合并前缀“app”为一个节点
    ├─ (结束，代表app)
    ├─ le (结束，代表apple)
    └─ e  (结束，代表ape)

核心优势：
- 空间更省：相同数据量下节点数更少，比如存储1000个有共同前缀的单词，Radix树可能只需要几百个节点，而Trie树需要几千个。
- 查找更快：因为节点层数减少，每次查找可以跳过连续的相同前缀，直接定位差异部分。

三、Radix树的结构细节（用ASCII图演示）

以单词集合 {“a”, “ab”, “abc”, “abd”, “ae”, “afg”} 为例：

root
               /   \
              a     e  # 首字母不同，分成两个分支
             / \
            ( )  b   # “a”单独成词（括号表示结束），然后是“ab”前缀
               / \
              c   d   # “abc”和“abd”
             /     \
            ( )     ( )
           /
          f
         /
        g
       /
      ( )  # “afg”

关键规则：
1. 节点存字符串：每个节点存的是一段连续字符（而非单个字符），比如“ab”“abc”。
2. 分裂条件：当某个前缀出现不同后缀时，才会分裂节点。例如“ab”后面跟着“c”和“d”，所以分裂成“abc”和“abd”。
3. 结束标记：节点若代表一个完整单词，会有结束标记（如括号）。

四、Radix树在计算机中的实际应用

1. 字符串检索：数据库索引、输入法联想词库（快速匹配前缀）。
2. 网络路由：路由器用Radix树存储IP地址路由表，快速查找目标地址。
3. SGLang中的RadixAttention：
4. 应用场景：在大语言模型中，不同请求可能有相同的前缀（如用户连续问类似问题），Radix树可以：

• 将相同前缀的KV缓存（模型推理时的中间结果）合并存储，避免重复计算。
• 比如用户问“今天天气如何”和“今天天气热吗”，前缀“今天天气”的KV缓存可复用，提升推理速度。

五、一句话总结Radix树的核心思想

“把重复的前缀打包成一个包裹，只在需要分叉的地方打开包裹”—— 就像快递分拣时，先按城市、再按区县、再按街道分层分拣，相同前缀的地址直接合并处理，效率更高。

如果需要更直观的动态演示，可以搜索“Radix Tree Visualization”，比如说：https://www.cs.usfca.edu/~galles/vi