gin-前缀树

xingliuhua 收录于笔记

2021-10-27 约 1543 字预计阅读 4 分钟

什么是“Trie 树”？

Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

我们有 6 个字符串，它们分别是：how，hi，her，hello，so，see。我们希望在里面多次查找某个字符串是否存在。如果每次查找，都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配，那效率就比较低。

可以先对这 6 个字符串做一下预处理，组织成 Trie 树的结构，之后每次查找，都是在 Trie 树中进行匹配查找。Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。最后构造出来的就是下面这个图中的样子。

当我们在 Trie 树中查找一个字符串的时候，比如查找字符串“her”，那我们将要查找的字符串分割成单个的字符 h，e，r，然后从 Trie 树的根节点开始匹配

Trie 树与散列表、红黑树的比较

一组字符串中查找字符串，Trie 树实际上表现得并不好。它对要处理的字符串有及其严苛的要求。

第一，字符串中包含的字符集不能太大。我们前面讲到，如果字符集太大，那存储空间可能就会浪费很多。即便可以优化，但也要付出牺牲查询、插入效率的代价。

第二，要求字符串的前缀重合比较多，不然空间消耗会变大很多。

第三，如果要用 Trie 树解决问题，那我们就要自己从零开始实现一个 Trie 树，还要保证没有 bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。

第四，我们知道，通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

综合这几点，针对在一组字符串中查找字符串的问题，我们在工程中，更倾向于用散列表或者红黑树。因为这两种数据结构，我们都不需要自己去实现，直接利用编程语言中提供的现成类库就行了。

实际上，Trie 树只是不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决。Trie 树比较适合的是查找前缀匹配的字符串，也就是类似开篇问题的那种场景。

gin数据结构

Engine 是 gin 框架的实例，在 Engine 结构中，trees 是一个数组，针对框架支持的每一种方法，都会创建一个节点。例如 GET、POST 是 trees 的两个元素。

//框架实例包含一个方法数数组
type Engine struct {
        trees            methodTrees
}
type methodTrees []methodTree
//方法树的定义
type methodTree struct {
        method string
        root   *node
}

我们看到，每一种请求方式对应一个树。

前缀树节点的定义

//path树的节点结构
type node struct {
        path      string
        indices   string
        children  []*node
        handlers  HandlersChain
        priority  uint32
        nType     nodeType
        maxParams uint8
        wildChild bool
        fullPath  string
}

path：表示当前节点的 path；
indices：通常情况下维护了 children 列表的 path 的各首字符组成的 string，之所以是通常情况，是在处理包含通配符的 path 处理中会有一些例外情况；
priority：代表了有几条路由会经过此节点，用于在节点进行排序时使用；
nType：是节点的类型，默认是 static 类型，还包括了 root 类型，对于 path 包含冒号通配符的情况，nType 是 param 类型，对于包含 * 通配符的情况，nType 类型是 catchAll 类型；
wildChild：默认是 false，当 children 是通配符类型时，wildChild 为 true；
fullPath：是从 root 节点到当前节点的全部 path 部分；如果此节点为终结节点 handlers 为对应的处理链，否则为 nil；maxParams 是当前节点到各个叶子节点的包含的通配符的最大数量。

节点创建程

案例1-普通的路径

engine := gin.Default()
	helloGroup := engine.Group("/hello")
	{
		helloGroup.Use(func(context *gin.Context) {

		})
		helloGroup.GET("/aaa/aa", func(context *gin.Context) {
			context.JSON(http.StatusOK, "ok")
		}) // 1
		helloGroup.GET("/aaa2/bb", func(context *gin.Context) {
			context.JSON(http.StatusOK, "ok")
		}) // 2
		helloGroup.GET("/bbb/aa", func(context *gin.Context) {
			context.JSON(http.StatusOK, "ok")
		}) // 3
		helloGroup.GET("/bbb/a/ccc", func(context *gin.Context) {
			context.JSON(http.StatusOK, "ok")
		}) // 4
	}

代码1处：

代码2处：

代码3处：

代码4处：

案例2-通配符

单条包含两个冒号通配 path 的一颗前缀树路由信息： “/user/:name/:age” name 和 age 是通配符的名字；这条路径形成的前缀树如下。

单条包含星号通配 path 的一颗前缀树

路由信息："/user/:name/*age" ，其中包含一个冒号通配符和一个星号通配符；这条路径形成的前缀树如下：

目录