4、前缀树（Trie）：从原理到实战的内存优化之路
说到路由匹配，我第一个想到的就是前缀树。
你想想看，一个路由器要处理成千上万条路由规则，每条规则还得快速匹配。用哈希表？内存是省了，但前缀匹配搞不定。用链表？匹配速度又太慢。这时候，Trie 树就派上用场了。
4.1 Trie 树原理：说白了就是共享前缀
Trie 树的核心思想很简单——把公共前缀合并到一起。比如 "api/user" 和 "api/admin"，它们共享 "api/" 这个前缀，那就只存一份。
每个节点代表一个字符，从根节点到叶子节点的路径，就是一条完整的路由规则。我习惯把这种结构叫做「字典树」，因为它查起来就像查字典一样快。
核心特性：
- 根节点不存数据，只做入口
- 每个节点存一个字符
- 从根到叶子拼起来就是完整路径
- 查找时间复杂度 O(L)，L 是路径长度
4.2 路由匹配场景：实战中的坑与解
我在项目中遇到过这样一个场景：一个网关系统要匹配 10 万条路由规则，其中还有通配符和参数占位符。用正则？慢得没法忍。用 Trie？嗯，得改造一下。
标准的 Trie 只做精确匹配，但路由需要支持：
- 精确匹配：/api/user/list → 直接命中
- 前缀匹配：/api/** → 匹配所有 /api/ 开头的路径
- 参数匹配：/user/:id → 把 id 提取出来
我当时的做法是：在节点上加一个「类型」标记。普通节点存字符，特殊节点存通配符或参数名。匹配时先走精确路径，没命中再回溯尝试通配符。
我的小技巧：匹配顺序很重要。先把精确匹配的节点放在前面，通配符放后面。这样大部分请求都能快速命中，不用回溯。
4.3 节点压缩优化：把 Trie 树「瘦身」
标准 Trie 有个大问题——内存爆炸。每个字符一个节点，10 万条路由下来，节点数轻松破百万。每个节点还要存 26 个（甚至更多）子节点指针，这谁顶得住？
我常用的优化手段有三种：
| 优化方式 | 原理 | 内存节省 | 适用场景 |
|---|---|---|---|
| 路径压缩 | 把连续的单子节点合并成一个节点 | 40%-60% | 路由路径较长时效果明显 |
| 哈希表替代数组 | 用 HashMap 存子节点，而不是固定数组 | 30%-50% | 字符集较大时 |
| 双数组 Trie | 用两个数组存储树结构 | 60%-80% | 静态路由表，不频繁增删 |
路径压缩是我最常用的。你想想看，"/api/v1/user/profile" 这个路径，如果每个字符都拆开，要建 20 多个节点。但压缩后，"/api/" 作为一个节点，"v1/" 作为一个节点，瞬间少了一大半。
注意：路径压缩后，插入和删除会变复杂。因为你要「拆节点」。我曾经在动态路由场景里用了路径压缩，结果每次更新路由都要重建子树，性能反而下降了。后来我改成只在启动时做一次压缩，运行时只做增量更新。
4.4 内存占用分析：到底吃了多少？
我们来算笔账。假设每条路由平均长度 20 个字符，10 万条路由：
- 标准 Trie：每个节点 72 字节（对象头 + 子节点数组 + 标记位），约 200 万个节点 → 144 MB
- 路径压缩后：节点数降到 40 万个，每个节点 80 字节（多了字符串字段）→ 32 MB
- 双数组 Trie：两个 int 数组，每个节点 8 字节 → 约 6.4 MB
看到了吧？从 144 MB 到 6.4 MB，差了 20 多倍。我接手过一个老项目，路由表占了 500 MB 堆内存，GC 频繁触发。换成双数组 Trie 后，直接降到 30 MB，GC 压力小了很多。
我的建议：
- 路由表不常变 → 用双数组 Trie，极致省内存
- 路由表频繁更新 → 用路径压缩 + 哈希表子节点
- 路由数量少于 1 万 → 直接用标准 Trie 也行，别过度优化
嗯，说到这我想起一个细节。双数组 Trie 虽然省内存，但构建过程比较麻烦。我一般会写个离线工具，在编译期就把路由表转成双数组格式，运行时直接加载。这样既省内存，又避免了构建时的性能开销。
最后说一句：Trie 树不是银弹。如果你的路由规则主要是精确匹配，哈希表可能更合适。但一旦涉及前缀匹配、通配符、参数提取，Trie 树就是最优解。关键是要选对优化策略，别为了省内存把性能搞崩了。
避坑指南：我曾经在内存紧张时强行用双数组 Trie，结果路由规则里有很多通配符，导致数组频繁扩容，性能反而比标准 Trie 还差。后来我加了个判断：如果通配符节点超过 10%，就改用路径压缩方案。