# Radix Tree 与 Gin 实现


> 简单介绍 Radix Tree 的原理与实现。

## 概览

#### Trie

Trie ，又叫字典树、前缀树（Prefix Tree）是一种多叉树结构，其核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。如下图：

![trie](trie.png)

可以看出，两个有公共前缀的关键字，在 Trie 中前缀部分的路径相同，所以Trie树又叫做前缀树。

Trie 的关键字`word`一般是字符串，而且 Trie 把每个关键字保存在一条路径上，而不是一个节点中。所以通常在实现时，会在节点中设置一个标志，用来标记该节点处是否构成一个关键字。Trie 具有以下特性：

1. 为了实现简单，根节点不包含字符，除根节点外的每一个子节点都只包含一个字符；
2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串；
3. 每个节点的所有子节点包含的字符互不相同。

Trie 的实现十分简单，其主要问题是树的高度依赖于存储的字符串的长度，查询与写入的时间复杂度为*O(m)*，m 为字符串的长度，因此搜索耗时会比较高。

#### Radix Tree

Radix Tree，也被称为压缩前缀树（Compact Prefix Tree）是一种空间优化的 Trie 数据结构。 如果树中某个节点是父节点的唯一子节点，那么该子节点将会与父节点进行合并，所以 Radix Tree 的节点可以包含一个或者多个元素。例如我们有`/App1/Config`和`/App/State`两个关键字，那么它们的存储结构可能是下面这样的：

![radix-tree](radix-tree.png)

总体来看，Radix Tree ，常被用于 IP 路由、字符串匹配等具有较多相同前缀且字符串长度有限的场景，下面将介绍 Gin Web 框架的路由实现。

## Gin 路由实现

Gin 框架为每种 HTTP 方法都维护了一个单独的 Radix Tree，所以不同方法的路由空间是隔离的。

```go
type methodTree struct {
	method string
	root   *node
}
```

Radix Tree 的每一个节点不仅保存了当前节点的字符串，也保存了一个路由的完整路径。除此之外还对查询过程进行了优化，`indices`字段保存了子节点的首个字符，以快速判断当前路径在哪个子节点中。

```go
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 写入数据的逻辑也不复杂，如果公共前缀长度小于当前节点保存的字符串长度，那么会分裂当前节点，否则递归进入子节点进行操作：

```go
// 代码有删减
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()`方法查询路由，在这个超长的函数中，其核心逻辑是是下面的广度优先遍历：

```go
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
					}
				}
      }
    }
  }
```