Gin 路由为什么快：Radix Tree 源码剖析

一、为什么路由匹配值得优化 @

路由匹配处于 HTTP 请求的最热路径上：每个请求进来，框架做的第一件事就是根据 URL 找到对应的 handler。它的实现方式直接决定了框架的性能下限。

先看几种朴素方案：

遍历 + 正则匹配：把路由表挨个试一遍，复杂度 O(n)，n 为路由数量。路由一多就不可接受。
Hash Map：静态路径可以 O(1) 精确匹配，但 /users/:id 这种参数路由无法用固定的 key 表示，Map 无能为力。
Radix Tree（压缩前缀树）：按路径前缀逐段匹配，复杂度只与路径长度有关，与注册的路由数量无关，同时天然支持参数和通配符。

Gin 选择了第三种。它的路由树 fork 自 httprouter，核心代码就在 tree.go 一个文件里，不到 500 行，非常值得精读。

二、从 Trie 到 Radix Tree @

Trie 的"单链"问题 @

用普通 Trie（字典树）存 /users、/users/:id 两条路由，每个节点只存一个字符：

root
└── 'u'
    └── 's'
        └── 'e'
            └── 'r'
                └── 's'
                    └── '/'
                        └── ':'
                            └── 'i'
                                └── 'd'

URL 中大部分字符的区分度极低，于是树里出现大量"只有一个子节点"的单链。节点多、指针跳转多，既浪费内存，又破坏 CPU 缓存的局部性。

Radix Tree 的压缩 @

Radix Tree 的思路很直接：把连续的单子节点链合并成一条边，边上存整个字符串片段：

root
└── "/users"           ← 整段存储，挂载 listUsers 的 handlers
    └── "/:id"         ← 参数节点，挂载 getUser 的 handlers

节点数从 9+ 个降到 2 个。匹配时不再逐字符比较，而是逐段做字符串前缀比较，比较次数和指针跳转次数都大幅下降。

三、Gin 的节点结构 @

Gin 中节点的定义（tree.go）：

type node struct {
	path      string        // 该节点对应的路径片段，如 "users"、":id"
	indices   string        // 静态子节点的首字符索引，用于快速定位
	wildChild bool          // 是否存在通配子节点（:param 或 *catchAll）
	nType     nodeType      // 节点类型：static / root / param / catchAll
	priority  uint32        // 权重，注册的路由越多值越大，用于子节点排序
	children  []*node       // 子节点，通配子节点固定放在末尾
	handlers  HandlersChain // 该节点挂载的处理函数链
	fullPath  string        // 完整路由路径，用于 panic 时输出友好的错误信息
}

几个关键设计：

path 存的是字符串片段而非单字符，这是 Radix Tree 区别于 Trie 的本质。
wildChild 是布尔标记，通配子节点固定存放在 children 切片的末尾。匹配时先按 indices 找静态子节点，找不到再看通配子节点。
indices 是静态子节点首字符的拼接。比如 indices = "sp" 表示有两个静态子节点，分别以 s、p 开头。匹配时用首字符做一次 O(子节点数) 的线性扫描，避免对每个子节点做完整字符串比较。
priority 记录子树挂载的路由数量，子节点按它降序排列，让"热门"分支排在前面被优先命中。

四、路由注册：addRoute @

插入的核心是最长公共前缀（longestCommonPrefix）和节点分裂（split）。

场景：树中已有 /users，再插入 /user。

Step 1: 计算最长公共前缀
  longestCommonPrefix("/user", "/users") = 5，即 "/user"

Step 2: 节点分裂
  因为 5 < len("/users")，原节点被"截断"：
  - 原节点 path 收缩为 "/user"，handlers 置空
  - 剩余部分 "s" 成为子节点，继承原有的 handlers、children 等全部状态

Step 3: 挂载新路由
  插入路径已被公共前缀完全消耗（5 == len("/user")），
  说明新路由正好落在分裂点上，直接把 handlers 挂到当前节点

结果：
root (path="/user", handlers=H_user)
└── "s" (handlers=H_users)

分裂的本质：当新插入路径把一个已有节点"拦腰截断"时，把该节点拆成"公共前缀"和"剩余部分"，原有状态全部下沉到剩余部分，保证已有路由不受影响。

如果插入路径在公共前缀之后还有剩余（比如已有 /users 再插入 /user/profile），剩余部分会作为新的子节点继续递归插入，遇到 :param 或 *catchAll 则创建对应类型的通配节点。其中 *catchAll 必须位于路径末尾，注册 /files/*filepath/suffix 这种路由会直接 panic。

五、路由匹配：getValue @

场景：注册了 /users、/users/:id、/users/:id/profile，请求 GET /users/123/profile。

匹配过程：

Step 1: 前缀匹配
  请求路径 "/users/123/profile" 与根节点 "/users" 前缀匹配，
  消耗 "/users"，剩余 "/123/profile"

Step 2: 定位子节点
  根节点无静态子节点，wildChild=true，
  进入 children 末尾的通配子节点 ":id"

Step 3: 参数提取
  ":id" 是 param 节点，截取到下一个 '/' 为止，
  得到参数 id="123"，剩余 "/profile"

Step 4: 继续向下
  ":id" 的子节点 "/profile" 精确匹配，返回该节点的 handlers
  → handlers + params{id: "123"}

每一步的查找顺序都是：先用 indices 在静态子节点中定位，失败后再尝试通配子节点。新版本的实现还带有回溯（backtracking）机制：当 param 分支匹配失败后，会跳过已尝试的节点回退重试，避免因静态分支与 param 分支交错导致的漏匹配。

六、冲突检测：为什么注册时会 panic @

这是 Radix Tree 在 Gin 中一个容易被误解的点：Gin 不存在"静态优先、参数其次"的运行时优先级选择，因为歧义路由在注册阶段就被拒绝（panic）了。

典型冲突：

r.GET("/users/:id", h1)
r.GET("/users/new", h2)
// panic: '/new' in new path '/users/new' conflicts with existing
// wildcard segment ':id' in existing prefix '/users/:id'

r.GET("/users/:id", h1)
r.GET("/users/:name", h2)
// panic: 同一位置的参数名必须一致

fullPath 字段就是为了让 panic 信息能带上完整路由路径，方便定位问题。

把歧义消灭在启动期是一个务实的设计取舍：运行时零冲突判断成本，换来的是匹配逻辑的最大简化，同时强制开发者写出无歧义的路由表。

七、复杂度与工程细节 @

操作	复杂度	说明
注册	O(k)	k = 路径长度
匹配	O(k)	与注册的路由总数无关

匹配耗时只取决于 URL 的长度和分段数：注册 100 条路由还是 10 万条路由，/users/123 的匹配路径都只有几跳。这也是 Gin 宣称路由匹配"零反射、低开销"的底气所在。

除了数据结构本身，还有几个工程层面的配合：

无哈希计算：匹配过程全是字符串前缀比较，不像 Map 需要对完整 key 做哈希。
priority 排序：热门分支排前面，减少静态子节点的扫描次数。
每棵 HTTP 方法一棵树：trees map[string]*node，GET、POST 各自独立，树更小更平。
零分配：路由表在启动时构建一次后只读；请求期的 Context、Params 通过 sync.Pool 复用，匹配本身不产生堆分配。

八、横向对比：Iris 的路由实现 @

同为 Go 生态的主流框架，Iris 的路由走了另一条路线。对照来看，Gin 的取舍会更清楚。

不压缩的分段 Trie @

Iris v12 的路由核心在 core/router/trie.go，代码注释注明它移植自作者的独立路由库 muxie 1.0.0：

type trieNode struct {
	parent                 *trieNode
	children               map[string]*trieNode // 子节点用 map 存
	hasDynamicChild        bool                  // 是否有动态子节点（参数或通配）
	childNamedParameter    bool                  // 有 :param 类型的子节点
	childWildcardParameter bool                  // 有 *wildcard 类型的子节点
	paramKeys              []string              // 参数名（不含 : 或 *）
	end                    bool                  // 是否为某条路由的终点
	// ...
}

与 Gin 的三个本质区别：

按"段"建树，不压缩。路径先按 / 切成 segment，每段一个节点，/users/:id/profile 就是 3 层节点，不存在合并与分裂。
子节点用 map[string] 定位，每段一次哈希查找，而不是 indices 线性扫描。
参数段归并为特殊 key：所有参数段统一存到 key ":" 下，通配段统一存到 "*" 下，参数名记录在路由终点的 paramKeys 里。

匹配策略：允许歧义，运行时裁决 @

Iris 每段的查找顺序：

静态子节点（map 命中）→ 命名参数节点（":"）→ 通配节点（"*"）
→ 全部失败：沿 parent 链回溯到最近的通配祖先（findClosestParentWildcardNode）

这意味着 /users/{id} 和 /users/new 可以共存：请求 /users/new 时静态分支先命中，请求 /users/123 时落到参数节点——Gin 直接 panic 的组合，Iris 选择全兼容。注册阶段还会先对路由表统一排序（子域名优先、层级深的优先、同层级静态优先），保证插入顺序不影响匹配结果。

此外 Iris 的路由还内置了一些 Gin 没有的能力：

macro 类型参数：{id:int}、{name:alphabetical} 等，以 filter handler 的形式在匹配后求值；
子域名路由：树按 (HTTP 方法, 子域名) 两个维度组织（trees []*trie），错误码处理走独立的 errorTrees；
运行时动态加路由：NewDynamicHandler 用 RWMutex 保护，支持服务运行中注册路由；
路径纠正：尾部斜杠 301/307 重定向，404 时可用 PathIntelligence 找到最接近的路径并跳转。

对比一览 @

维度	Gin	Iris
数据结构	压缩 Radix Tree，边上存片段	普通 Trie，每段一个节点
子节点定位	`indices` 首字符扫描 + slice	`map[string]` 哈希查找
歧义路由	注册时 panic	允许共存，静态 > 参数 > 通配 + 回溯
参数能力	`:id`、`*filepath`	`{id}`、`{filepath:path}`、macro 类型参数
分树维度	每个 HTTP 方法一棵	每个 (方法, 子域名) 一棵
路由变更	构建后只读	可选运行时动态注册
参数存储	复用 Context 固定数组，零分配	`RequestParams.Set` 增长切片

实测数据 @

同一张路由表（20 条，静态/参数/通配混合），在本机（Ryzen 7 5800U，Go 1.26）对两者的 ServeHTTP 完整分发路径做 benchmark：

场景	Gin	Iris
静态路由	40 ns/op, 0 alloc	66 ns/op, 0 alloc
单参数路由	42 ns/op, 0 alloc	120 ns/op, 1 alloc
三参数深层路由	71 ns/op, 0 alloc	310 ns/op, 4 alloc
通配路由	48 ns/op, 0 alloc	151 ns/op, 2 alloc

差距来源可以和实现一一对应：

参数分配：Gin 的 Params 复用 sync.Pool 中 Context 的固定容量数组，全程零分配；Iris 每个参数都要增长切片，1 参数 1 alloc、3 参数 4 alloc，GC 压力下差距会进一步放大。
哈希 vs 前缀比较：Iris 每段一次 map 哈希，路径越深次数越多；Gin 是 indices 上几个字节的小循环加整段字符串比较，没有哈希计算。这是深层参数路由差距拉大到 4 倍的主因。
节点密度：不压缩意味着更多节点、更多指针跳转，缓存局部性更差。

不过要把数字放回语境：两者的绝对开销都在几十到几百纳秒，真实 handler 只要碰一次 I/O，路由差异就会被淹没。Iris 多付的代价换来的是路由全兼容、类型参数、动态注册这些能力——这是特性与性能之间的交换，而非单纯的优劣。

九、总结 @

Radix Tree 通过压缩单链，用少量节点表示大量共享前缀的路由，兼顾了 Trie 的查找效率和内存占用。
Gin 的实现要点：path 存片段、indices 加速静态定位、通配子节点固定置于 children 末尾、priority 排序。
注册时做节点分裂和冲突检测，匹配时逐段前缀比较 + 参数提取，全程 O(k)。
歧义路由在启动期 panic，而不是留到运行时按优先级"猜"，这是值得借鉴的设计思路。
横向看，Iris 用"不压缩 + map 定位 + 运行时裁决"换取路由表达的兼容性和丰富功能，Gin 用"压缩 + panic + 零分配"换取极限性能——同一问题两端的不同取舍。

参考资料：

Gin 源码： tree.go
算法原型： julienschmidt/httprouter
Iris 源码： core/router/trie.go、 core/router/handler.go
Iris 路由原型： kataras/muxie
Radix Tree 维基： Radix tree - Wikipedia