[Gin]框架底层实现理解(一)

前言：路由原理———压缩字典

这边简单讲一下gin非常重要的一个基点，也就是他作为go web框架的一个亮点

也就是Trie树和压缩字典算法

gin 通过树来存储路由，讲路由的字符拆解为一个个的结点，在获取handler函数时，会根据路由来获取对应的结点，结点中包含了handler函数，根据结点来获取对应的handler函数

主要就是压缩字典算法：

正常的trie树的存储单个结点，一个结点一个字符，这样是非常耗空间的，但是如果使用压缩字典算法则是通过先找到共同公共前缀，再去找子结点，如此重复以上两个步骤，期间会对结点进行切分和重组形成新的结点，极大的节省了存储空间 

比如上图没有使用压缩字典树算法路由 /acd /at /bee 形成的树形结构，每个字母的父亲节点就是它的前一个字母

Trie树的三个性质：

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符

• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串

• 每个节点的所有子节点包含的字符都不相同

那么有了这样的一颗树，查找单词就变得很简单，从根节点开始向下匹配，如果匹配到单词的前缀就沿着该节点接着往下匹配，直到完全匹配到单词。

但是trie树的每个节点只能存储一个字符，这意味着面对较长的字符串仍然要向下探寻多个节点，这存在着浪费，因此就有了压缩字典树，

压缩字典树，是trie树的一种，也称单词查找树、前缀树，善于进行字符串的检索、取字符串最长公共前缀、以及排序，常应用在搜索引擎中例如百度输入某个字可能自动弹出能匹配到的单词出来。

以下分别是Trie树和压缩字典树：

 

显而易见的相同路径下，结点数量便少了很多

压缩字典树的特质使得其用于单词前缀查找时更快。这也恰巧就是一个高性能的路由匹配算法需要的。因此Gin使用其作为路由算法。

type node struct {path      string // 存储着节点的字符串indices   string // 存储着下级子节点的前缀索引 这边是作为数组切片用，按照子结点顺序，抽取其所有子结点首字符放入这里wildChild bool   //进行模糊匹配，例如有些是/user/:pid 这类的url，存储的结点遍历到/:pid时候就会判断是不是模糊匹配//如果你的url是user/1234 那么就会根据这个参数进行模糊匹配也就是 将1234填补:pid的位置nType     nodeType 
// nType 节点类型：
// static nodeType = iota // default，默认类型
// root 根节点
// param 参数，例如:id这样的通配符
// catchAll 全匹配priority  uint32  // 优先级  这个树的结点有权重比，一般是越上面的结点权重越高，具体看实现children  []*node // 子节点, 至少有一个， :param 类型的节点会在列表的末尾handlers  HandlersChain // 匹配该节点的路由的处理函数  一个结点可以有多个handle函数，也就是其名字带chain的意义fullPath  string        // 从根节点到该节点的完整路径  relativePath
}

 

下面通过引用一个博主的流程图直观解释添加结点的流程

插入操作 图解一串子串插入压缩trie过程，/,/serach,/support,/blog , 在httprouter上截的一段例子，我们只插到/blog

 插入/serach

 

插入/support

 

插入/blog

同第二步，查询后直接插入blog

——查询操作——

1、先找共同前缀。 2、再找目录。 3、循环上面两步，直到当前path相等。

gin中还根据不同的请求方法分为不同的树，例如get，post等方法都有各自独立的树，但是都同属于同一个根节点