前缀树——以Gin路由为例

前缀树是父节点是子节点前缀的N叉树。

其主要性质是

• 根节点不包括字符
• 每个节点的子节点字符不同
• 节点对应的字符串为从根节点到该节点路径上字符的组合

在gin中也存在着非常巧妙运用前缀树进行路由匹配的结构，本文将以gin路由为例学习一下前缀树

本文代码皆是参考gin@v1.7.4版本源码所构建的更适合理解改造版，并且省略了诸如标记是否是通配符的node wildChild等属性和方法

Gin前缀树结构

gin为每个方法都创建了前缀树。每个前缀树包含了根节点，以及方法名。

每个节点包含了

• 当前路径
• 全路径：也就是根节点到该节点的路径组成的字符串
• 优先级：子节点越多优先级越高
• 子节点：
• 子节点首字母组成的字符串：用于快速确认新增或者查询的路径是否存在了

type engine struct {trees methodsTrees
}type methodsTrees []methodTreetype methodTree struct {method stringroot   *node
}type node struct {// 当前节点pathpath string// 子节点首字符组成的stringindices string// 按照优先级排序的子节点children []*node// 优先级priority uint32// 根节点到该节点的字符串fullPath string// 处理器handlers []Handler
}// 遍历树，若存在对应方法所在的树就返回
func (t methodsTrees) get(method string) *node {for _, tree := range t {if tree.method == method {return tree.root}}return nil
}

插入

前缀树插入过程如下

1. 若根节点为空，直接设置根节点路径为新增路径，并返回
2. 若当前节点路径与新增路径不存在公共前缀，那么就使当前节点的所有子节点作为当前节点的其中一个子节点，新增路径为另一个子节点
3. 若新增路径的非公共前缀首字符在当前节点的子节点存在，那么就将该新增路径插入到该子节点，并返回
4. 在新增路径与节点路径完全匹配的时候，覆盖当前节点处理器和路径

func (n *node) addRoute(path string, handlers []Handler) {fullPath := pathn.priority++// 若为空节点，则直接插入子节点if len(n.path) == 0 && len(n.children) == 0 {n.path = pathn.fullPath = fullPathn.handlers = handlersreturn}// 根据路径插入到节点n.addChild(path, fullPath, 0, handlers)
}func (n *node) addChild(path, fullPath string, parentFullPathIndex int, handlers []Handler) {// 找到新增路径与节点路径的最长公共前缀i := longestCommonPrefix(path, n.path)// 节点的path不是最长公共前缀，分裂原子节点和新增节点if i < len(n.path) {child := &node{path:     n.path[i:],indices:  n.indices,children: n.children,priority: n.priority - 1,fullPath: n.fullPath,}n.children = []*node{child}n.indices = string(n.path[i])n.path = path[:i]n.fullPath = fullPath[:parentFullPathIndex+i]}// 在新增路径存在公共前缀时，添加含有该路径的子节点if i < len(path) {path = path[i:]c := path[0]// 若该路径的非公共前缀首字符在节点children已经存在，那么就将该节点添加到子节点中for j, max := 0, len(n.indices); j < max; j++ {if c == n.indices[j] {parentFullPathIndex += len(n.path)j = n.incrementChildPriority(j)n.children[j].addChild(path, fullPath, parentFullPathIndex, handlers)return}}// 若该路径的非公共前缀首字符在节点children不存在，就直接添加为节点的子节点n.indices += string(c)child := &node{fullPath: fullPath, path: path, handlers: handlers}n.children = append(n.children, child)n.incrementChildPriority(len(n.indices) - 1)return}// 路径与节点路径完全匹配时，直接覆盖原全路径和处理器n.handlers = handlersn.fullPath = fullPathreturn
}// 增加子节点的优先级
func (n *node) incrementChildPriority(pos int) int {// 增加该子节点的优先级cs := n.childrencs[pos].priority++prio := cs[pos].priority// 重新根据优先级排序newPos := posfor ; newPos > 0 && cs[newPos-1].priority < prio; newPos-- {cs[newPos-1], cs[newPos] = cs[newPos], cs[newPos-1]}// 重新组合indicesif newPos != pos {n.indices = n.indices[:newPos] + n.indices[pos:pos+1] + n.indices[newPos:pos] + n.indices[pos+1:]}return newPos
}func (e *engine) addRoute(method, path string, handlers []Handler) {// 1. 根据方法获取对应的前缀树。若root为nil，则初始化root := e.trees.get(method)if root == nil {root = &node{fullPath: "/",}e.trees = append(e.trees, methodTree{method: method,root:   root,})}// 2. 添加路径到前缀树root.addRoute(path, handlers)
}func longestCommonPrefix(a, b string) int {i := 0max := minInt(len(a), len(b))for i < max && a[i] == b[i] {i++}return i
}func minInt(x, y int) int {if x < y {return x}return y
}

匹配

标记为tsr就是在为true情况下并且可以Redirect Trailing Slash，那么就可以重定向到原url附加’/'的地址

前缀树匹配过程如下

1. 若路径不完全匹配当前节点路径，尝试找到匹配的子节点，并在子节点中继续匹配；若无法找到匹配子节点且无法匹配的字符为’/'，那就标记tsr并返回
2. 若路径完全匹配当前节点路径。在处理器有效的情况下，就返回匹配到的处理器。若无效就尝试找到仅含有’/'路径的子节点，标记为tsr并返回
3. 若路径完全不匹配当前节点路径，返回空

type nodeValue struct {handlers []Handlertsr      bool
}func (n *node) getValue(path string) *nodeValue {prefix := n.path// 若路径不完全匹配当前节点路径if len(path) > len(prefix) {// 若路径存在该前缀if path[:len(prefix)] == prefix {path = path[len(prefix):]// 尝试找到匹配该路径的子节点idxc := path[0]for i := 0; i < len(n.indices); i++ {if idxc == n.indices[i] {n.children[i].getValue(path)}}// 若无法找到匹配子节点且无法匹配的路径为'/'，那么就标记tsrreturn &nodeValue{tsr: path == "/" && n.handlers != nil,}}}// 路径与节点路径完全匹配if path == prefix {// 若节点处理器存在，则返回if n.handlers != nil {return &nodeValue{handlers: n.handlers,}}for i := 0; i < len(n.indices); i++ {// 若存在'/'路径的子节点，则标记tsrif n.indices[i] == '/' {child := n.children[i]return &nodeValue{tsr: len(child.path) == 1 && child.handlers != nil,}}}}return nil
}