路由表最长前缀匹配为什么可以用 Trie？
简化版
IP 路由表匹配的是「目标 IP 和哪条网络前缀最长匹配」。
可以把 IP 地址看成二进制字符串，用 0-1 Trie 存路由前缀。查询时按目标 IP 的二进制位从根往下走，沿途记录最后一次遇到的路由项。走不下去或走完后，最近记录的路由项就是最长前缀匹配结果。
这就是 Trie 在网络路由中的典型应用。
详细版
例如路由表里有：
10.0.0.0/8
10.1.0.0/16
10.1.2.0/24目标 IP 是 10.1.2.9，它同时匹配这 3 条前缀，但最长的是 /24。
0-1 Trie 的做法是：
- 把每条路由前缀按二进制位插入；
- 前缀结束节点保存下一跳信息；
- 查询 IP 时一路按 bit 走；
- 每遇到一个带路由信息的节点就更新答案。
| 操作 | 复杂度 |
|---|---|
| 插入 IPv4 前缀 | 最多 32 步 |
| 查询 IPv4 地址 | 最多 32 步 |
完整版教学
1. 什么是最长前缀匹配
路由表不是精确匹配完整 IP，而是匹配网络前缀。
前缀越长，范围越小，也越具体。
例如：
| 路由 | 覆盖范围直觉 |
|---|---|
/8 | 很大范围 |
/16 | 更具体 |
/24 | 更具体 |
如果一个目标 IP 同时匹配多条路由，要选择前缀最长的那条。
2. 为什么可以把 IP 看成二进制字符串
IPv4 地址本质是 32 位二进制数。
例如：
10.1.2.9 = 00001010 00000001 00000010 00001001路由前缀 /24 就表示前 24 位固定。
因此路由匹配可以转成二进制前缀匹配，Trie 正好擅长前缀问题。
3. 0-1 Trie 如何存路由
每个节点最多有两个孩子：
child[0]
child[1]插入 10.1.2.0/24 时，只插入前 24 位。插入结束的节点保存路由信息，比如下一跳或出接口。
路由 Trie 的节点不一定都是完整 IP，很多节点表示的是网络前缀。
4. 查询时为什么要记录沿途答案
查询目标 IP 时，会从最高位开始往下走。
沿途可能遇到多个带路由信息的节点：
/8 -> 可用答案
/16 -> 更长答案
/24 -> 更长答案因为越往下前缀越长，所以每次遇到路由信息就更新答案。最后记录的就是最长前缀匹配。
5. 查询伪代码
伪代码如下：
match(ip):
cur = root
ans = defaultRoute
for bit in bits(ip):
if cur.route != null:
ans = cur.route
if cur.child[bit] == null:
break
cur = cur.child[bit]
if cur.route != null:
ans = cur.route
return ans最后一次检查是为了覆盖走到终点节点正好有路由的情况。
6. 默认路由怎么处理
默认路由是：
0.0.0.0/0它匹配所有 IP，前缀长度为 0。
在 Trie 中可以把默认路由存在 root 节点。查询一开始的 ans 就可以是 root 的路由信息。
7. 工程上为什么还会优化
简单 0-1 Trie 每次 IPv4 查询最多 32 步，已经不错。
但真实路由表可能非常大，还要考虑缓存、更新、IPv6 的 128 位长度等因素，所以会有压缩 Trie、多比特 Trie、LC-Trie 等优化。
| 优化方向 | 目的 |
|---|---|
| 路径压缩 | 减少单孩子链 |
| 多比特步进 | 每次看多位 |
| 缓存友好布局 | 提高查询吞吐 |
8. 常见误区与追问
- 误区：路由匹配是精确匹配 IP。 路由匹配通常是网络前缀匹配，不是完整地址匹配。
- 误区：匹配到第一条路由就返回。 要继续走，选择最长前缀对应的路由。
- 误区：Trie 只能处理字符串。 IP 的二进制位也可以作为 Trie 的字符集。
- 追问：默认路由放在哪里？ 可以放在 root 节点，表示长度为 0 的前缀。
- 追问：IPv6 怎么办？ 原理相同，但地址是 128 位，更需要压缩或多比特优化。