3、路由查找算法：线性查找、二分查找、最长前缀匹配(LPM)算法详解
路由查找，说白了就是路由器收到一个数据包后，得赶紧查一下转发表，决定从哪个口扔出去。这个动作快不快，直接决定了整个网络的转发性能。我这些年调过不少路由器的转发面，说实话，很多性能瓶颈就卡在这一步。
今天咱们就把三种最核心的查找算法掰开揉碎讲清楚。你想想看，从最简单的线性查找，到稍微快点的二分查找，再到真正生产环境里用的最长前缀匹配（LPM），这中间其实是一条很清晰的演进路线。
3.1 线性查找：最朴素，但也最慢
线性查找的思路简单到令人发指——把路由表当成一个列表，从头到尾挨个比对。匹配到了就返回，没匹配到就继续往下走。
我刚开始做网关开发时，第一版原型就用的这个。当时觉得，路由表才几百条，能慢到哪去？结果一压测，吞吐量直接崩了。
// 线性查找伪代码
function linearSearch(packet, routingTable) {
for (entry in routingTable) {
if (packet.destIP == entry.network) {
return entry.nextHop;
}
}
return null; // 没找到，走默认路由
}
这里有个坑。你想想看，如果路由表有 10 万条，最坏情况下你得比 10 万次。一个核心路由器每秒要处理几百万个包，这谁顶得住？
所以线性查找只适合两种情况：一是路由表极小（几十条以内），二是你根本不在乎性能。生产环境？别想了。
3.2 二分查找：快是快了，但有个致命问题
二分查找大家都很熟，前提是数据得有序。路由表按目的网络地址排好序，然后每次取中间值比对，根据大小决定往左还是往右。
// 二分查找伪代码（假设路由表已按网络地址排序）
function binarySearch(packet, sortedTable) {
left = 0;
right = sortedTable.length - 1;
while (left <= right) {
mid = (left + right) / 2;
if (packet.destIP == sortedTable[mid].network) {
return sortedTable[mid].nextHop;
} else if (packet.destIP < sortedTable[mid].network) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return null;
}
嗯，这里要注意。二分查找确实快，但它有个致命问题——它只能做精确匹配。而路由查找的本质是最长前缀匹配。
举个例子。目标 IP 是 192.168.1.100，路由表里有两条：
- 192.168.0.0/16 → 下一跳 A
- 192.168.1.0/24 → 下一跳 B
按最长前缀匹配，应该匹配 /24 那条，走下一跳 B。但二分查找只能精确匹配 192.168.1.100，如果表里没有这个精确条目，它就返回 null 了。你想想看，这合理吗？
我见过有人强行用二分查找做路由，方法是把所有可能的前缀长度都展开成精确条目。比如 /16 展开成 65536 条 /32 的精确路由。结果呢？路由表从几千条膨胀到几百万条，内存爆了，更新也慢得要死。
3.3 最长前缀匹配（LPM）：这才是真·路由查找
最长前缀匹配，英文叫 Longest Prefix Match，简称 LPM。它的核心思想很简单：匹配所有能匹配的条目，选前缀最长的那个。
为什么非得是最长的？因为前缀越长，表示网络范围越小，路由越精确。你想想看，去北京和去海淀区，肯定是后者的路径更具体。
3.3.1 LPM 的查找逻辑
假设目标 IP 是 10.1.2.100，路由表如下：
| 前缀 | 下一跳 |
|---|---|
| 0.0.0.0/0 | 默认网关 |
| 10.0.0.0/8 | Router A |
| 10.1.0.0/16 | Router B |
| 10.1.2.0/24 | Router C |
查找过程是这样的：
- 先看 /0，匹配（所有 IP 都匹配默认路由）
- 再看 /8，10.1.2.100 在 10.0.0.0/8 范围内，匹配
- 再看 /16，10.1.2.100 在 10.1.0.0/16 范围内，匹配
- 再看 /24，10.1.2.100 在 10.1.2.0/24 范围内，匹配
- 选最长的 /24，下一跳是 Router C
你看，四条都匹配，但选最长的那条。这就是 LPM 的精髓。
3.3.2 工业界怎么实现 LPM？
最经典的实现是 Trie 树（字典树），也叫前缀树。把每个路由条目按二进制位插入树中，查找时顺着 IP 的每一位往下走，沿途记录最后一个匹配的节点。
// Trie 树节点结构（简化版）
class TrieNode {
TrieNode left; // 0 分支
TrieNode right; // 1 分支
RouteEntry route; // 如果当前节点是路由条目，存这里
}
// LPM 查找
function lpmLookup(root, ip) {
node = root;
bestMatch = null;
for (bit in ip) {
if (node.route != null) {
bestMatch = node.route; // 记录当前匹配
}
if (bit == 0) {
node = node.left;
} else {
node = node.right;
}
if (node == null) break;
}
return bestMatch;
}
这个复杂度跟路由表大小无关，只跟 IP 地址长度有关。32 次比较就能搞定，比 O(log n) 还稳定。我参与过一个核心路由器的项目，路由表 80 万条，用 Trie 树查找，单次查找时间稳定在 100 纳秒以内。
3.3.3 实际生产中的优化
纯 Trie 树有个问题——内存占用大。每个节点都要存两个指针，80 万条路由可能吃掉几百 MB 内存。所以工业界做了很多优化：
- 压缩 Trie（Patricia Trie）：跳过连续的相同位，减少节点数
- 多比特 Trie：一次查 4 位或 8 位，用查表代替逐位比较
- TCAM（三态内容寻址存储器）：硬件方案，一个时钟周期出结果，但贵且功耗高
3.4 三种算法对比总结
| 算法 | 时间复杂度 | 支持 LPM | 适用场景 |
|---|---|---|---|
| 线性查找 | O(n) | 是 | 小型路由表（<100条） |
| 二分查找 | O(log n) | 否（需精确匹配） | 基本不用于路由查找 |
| Trie 树（LPM） | O(W) | 是 | 生产环境首选 |
最后说一句。路由查找算法看着简单，但真正做好很难。我见过太多人一上来就怼 Trie 树，结果内存爆了；也有人死磕线性查找，觉得路由表不大就没事。我的建议是：先搞清楚你的路由表规模、更新频率、硬件资源，再选方案。没有银弹，只有最适合的。
下一章咱们聊聊路由表的内存布局和缓存优化，那才是真正拉开性能差距的地方。