简单介绍 Radix Tree 的原理与实现。
概览
Trie
Trie ，又叫字典树、前缀树（Prefix Tree）是一种多叉树结构，其核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。如下图：
可以看出，两个有公共前缀的关键字，在 Trie 中前缀部分的路径相同，所以Trie树又叫做前缀树。
Trie 的关键字word一般是字符串，而且 Trie 把每个关键字保存在一条路径上，而不是一个节点中。所以通常在实现时，会在节点中设置一个标志，用来标记该节点处是否构成一个关键字。Trie 具有以下特性：
- 为了实现简单，根节点不包含字符，除根节点外的每一个子节点都只包含一个字符；
- 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串；
- 每个节点的所有子节点包含的字符互不相同。
Trie 的实现十分简单，其主要问题是树的高度依赖于存储的字符串的长度，查询与写入的时间复杂度为O(m)，m 为字符串的长度，因此搜索耗时会比较高。
Radix Tree
Radix Tree，也被称为压缩前缀树（Compact Prefix Tree）是一种空间优化的 Trie 数据结构。 如果树中某个节点是父节点的唯一子节点，那么该子节点将会与父节点进行合并，所以 Radix Tree 的节点可以包含一个或者多个元素。例如我们有/App1/Config和/App/State两个关键字，那么它们的存储结构可能是下面这样的：
总体来看，Radix Tree ，常被用于 IP 路由、字符串匹配等具有较多相同前缀且字符串长度有限的场景，下面将介绍 Gin Web 框架的路由实现。
Gin 路由实现
Gin 框架为每种 HTTP 方法都维护了一个单独的 Radix Tree，所以不同方法的路由空间是隔离的。
1
2
3
4
|
type methodTree struct {
method string
root *node
}
|
Radix Tree 的每一个节点不仅保存了当前节点的字符串，也保存了一个路由的完整路径。除此之外还对查询过程进行了优化，indices字段保存了子节点的首个字符，以快速判断当前路径在哪个子节点中。
1
2
3
4
5
6
7
8
9
10
|
type node struct {
path string // 该节点对应的 path
indices string // 子节点 path 的第一个字符的集合
wildChild bool // 子节点是否包含通配符节点
nType nodeType // 当前节点类型
priority uint32 // 优先级，子节点、子子节点等注册的handler数量
children []*node // 子节点集合，每个 children 中只能包含一个参数节点，并且在集合的最后一位
handlers HandlersChain // 处理函数链
fullPath string // 完整路径
}
|
路由注册
Radix Tree 写入数据的逻辑也不复杂，如果公共前缀长度小于当前节点保存的字符串长度，那么会分裂当前节点，否则递归进入子节点进行操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
// 代码有删减
func (n *node) addRoute(path string, handlers HandlersChain) {
fullPath := path
n.priority++
// 空节点直接插入
if len(n.path) == 0 && len(n.children) == 0 {
n.insertChild(path, fullPath, handlers)
n.nType = root
return
}
parentFullPathIndex := 0
walk:
for {
// 找到最长的公共前缀
i := longestCommonPrefix(path, n.path)
if i < len(n.path) {
// 如果公共前缀长度小于当前节点保存的字符串长度，分裂当前节点
}
// 插入子节点
if i < len(path) {
path = path[i:]
c := path[0]
n.insertChild(path, fullPath, handlers)
return
}
return
}
}
|
路由匹配
Gin 通过node.getValue()方法查询路由，在这个超长的函数中，其核心逻辑是是下面的广度优先遍历：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
walk: // Outer loop for walking the tree
for {
prefix := n.path
if len(path) > len(prefix) {
if path[:len(prefix)] == prefix {
path = path[len(prefix):]
// Try all the non-wildcard children first by matching the indices
idxc := path[0]
for i, c := range []byte(n.indices) {
if c == idxc {
n = n.children[i]
continue walk
}
}
}
}
}
|
