基数树
这次学习的是 Gin 中的路由，在学习源码一种我们看到了 Gin 的路由是它的特色。然而基础数据使用了基数树也提供了性能的保障。因为路由这部分比较独立而且逻辑相对复杂，所以需要单独学习。
首先我们需要了解的是基数树，百度百科中的解释
其中有一个图可以让我们更加直观的看到数据是如何存储的。
基数树，相当于是一种前缀树。对于基数树的每个节点，如果该节点是确定的子树的话，就和父节点合并。基数树可用来构建关联数组。
在上面的图里也可以看到，数据结构会把所有相同前缀都提取 剩余的都作为子节点。
基数树在 Gin 中的应用
从上面可以看到基数树是一个前缀树，图中也可以看到数据结构。那基数树在 Gin 中是如何应用的呢？举一个例子其实就能看得出来
router.GET(“/support”, handler1)
router.GET(“/search”, handler2)
router.GET(“/contact”, handler3)
router.GET(“/group/user/”, handler4)
router.GET(“/group/user/test”, handler5)
最终的内存结构为:
/ (handler = nil, indices = "scg")
s (handler = nil, indices = "ue")
upport (handler = handler1, indices = "")
earch (handler = handler2, indices = "")
contact (handler = handler3, indices = "")
group/user/ (handler = handler4, indices = "u")
test (handler = handler5, indices = "")可以看到 router 使用 get 方法添加了 5 个路由，实际存储结果就是上面显示的。我特地在后面加上了每个节点中的 handler 和 indices。indices 是有序保存所有子节点的第一个字符形成的字符串。为什么要特意突出这个字段，因为在查找子节点下面是否包含 path 的时候不需要循环子节点，只需要循环这个字段就可以知道是否包含。这样的操作也可以提升一些效率。
源码查看
先看一下节点的对象的定义和如何调用的，需要注意的是 indices 这个字段 上面已经提到了它的作用
type node struct {
// 保存这个节点上的 URL 路径
// 例如上图中的 search 和 support, 共同的 parent 节点的 path="s"
// 后面两个节点的 path 分别是 "earch" 和 "upport"
path string
// 判断当前节点路径是不是参数节点, 例如上图的:post 部分就是 wildChild 节点
wildChild bool
// 节点类型包括 static, root, param, catchAll
// static: 静态节点, 例如上面分裂出来作为 parent 的 s
// root: 如果插入的节点是第一个, 那么是 root 节点
// catchAll: 有 * 匹配的节点
// param: 除上面外的节点
nType nodeType
// 记录路径上最大参数个数
maxParams uint8
// 和 children[]对应, 保存的是分裂的分支的第一个字符
// 例如 search 和 support, 那么 s 节点的 indices 对应的 "eu"
// 代表有两个分支, 分支的首字母分别是 e 和 u
indices string
// 保存孩子节点
children []*node
// 当前节点的处理函数
handle Handle
// 优先级
priority uint32
}
//RouterGrou 实现的 GET 方法调用了 handler
func (group *RouterGroup) GET(relativePath string, handlers ...HandlerFunc) IRoutes {return group.handle("GET", relativePath, handlers)
}
func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {
// 方法计算出路径，把 group 中的 basepath 和 relativepath 合并在一起
absolutePath := group.calculateAbsolutePath(relativePath)
// 合并 handler 把 group 中添加的中间件和传入的 handlers 合并起来
handlers = group.combineHandlers(handlers)
// 调用 addRoute 添加 router
group.engine.addRoute(httpMethod, absolutePath, handlers)
return group.returnObj()}接下来我们需要看的是 addRoute 这个方法了，方法体比较长。其实大多的逻辑都在处理带参数的节点，真正核心的逻辑其实并不多。我把主要的逻辑都写上了注释应该还是比较容易理解的。如果看不懂其实一步步 debug 几次也能帮助理解。
func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {assert1(path[0] == '/', "path must begin with'/'")
assert1(method != "","HTTP method can not be empty")
assert1(len(handlers) > 0, "there must be at least one handler")
debugPrintRoute(method, path, handlers)
// 获取 method 的树的根节点，每个 method 都有一个根节点，比如 GET，POST 都会维护一个根节点
root := engine.trees.get(method)
// 如果没有则创建一个节点
if root == nil {root = new(node)
engine.trees = append(engine.trees, methodTree{method: method, root: root})
}
// 正式添加路由
root.addRoute(path, handlers)
}
func (n *node) addRoute(path string, handlers HandlersChain) {
// 记录原始 path
fullPath := path
n.priority++
// 统计 path 中包含多少参数 就是判断 `：`，`*` 的数量 最多 255 个
numParams := countParams(path)
// 判断节点是否为空
if len(n.path) > 0 || len(n.children) > 0 {
walk:
for {
// 更新最大参数数量
if numParams > n.maxParams {n.maxParams = numParams}
// 找到相同前缀 循环次数 是取 path 和 n.path 长度的小那个长度
i := 0
max := min(len(path), len(n.path))
// 循环判断是否字符相同，相同则 i ++ 直到最后
for i < max && path[i] == n.path[i] {i++}
// 判断是否有前缀相同，如果有相同的则把目前这个节点提取出来作为子节点
// 再把相同前缀的 path 部分作为 父节点
// 比如 n 的 path = romaned 现在新增路由的 path = romanus 相同前缀为 roman
// 步骤为：//1. 提取 ed 新建一个 child 节点 把原来 n 的属性都复制过去
//2. 把原来的 n 的 path 改为相同前缀：roman 为 indices 添加 子节点的第一个字符:e
if i < len(n.path) {
child := node{path: n.path[i:],
wildChild: n.wildChild,
indices: n.indices,
children: n.children,
handlers: n.handlers,
priority: n.priority - 1,
}
// Update maxParams (max of all children)
for i := range child.children {if child.children[i].maxParams > child.maxParams {child.maxParams = child.children[i].maxParams
}
}
n.children = []*node{&child}
// []byte for proper unicode char conversion, see #65
n.indices = string([]byte{n.path[i]})
n.path = path[:i]
n.handlers = nil
n.wildChild = false
}
// 原先的节点 n 现在已经分成 2 个节点了 结构为：//roman 父节点
// ed 子节点[0]
// 那么现在需要把传入的路由添加到这个父节点中
// 最终结构为
//roman 父节点
// ed 子节点[0]
// us 子节点[1]
// 其中还有一些情况需要自调用 相当于递归 举例说明：//roman
// ed
// uie
// 当判断父节点 n 本来就有一个 uie 子节点 这时候 uie 和 us 又有相同前缀 u 这个时候需要把这个 u 再次提取出来作为父节点 所以需要递归调用 walk
// 最终结果为 三层结构
//roman
// ed
// u
// ie
// s
// 还有一种情况是如果是带有参数的路由 则也会再次调用 walk
if i < len(path) {path = path[i:]
if n.wildChild {n = n.children[0]
n.priority++
// Update maxParams of the child node
if numParams > n.maxParams {n.maxParams = numParams}
numParams--
// Check if the wildcard matches
if len(path) >= len(n.path) && n.path == path[:len(n.path)] {
// check for longer wildcard, e.g. :name and :names
if len(n.path) >= len(path) || path[len(n.path)] == '/' {continue walk}
}
panic("path segment'" + path +
"'conflicts with existing wildcard'" + n.path +
"'in path'" + fullPath + "'")
}
c := path[0]
// slash after param
if n.nType == param && c == '/' && len(n.children) == 1 {n = n.children[0]
n.priority++
continue walk
}
// Check if a child with the next path byte exists
for i := 0; i < len(n.indices); i++ {if c == n.indices[i] {i = n.incrementChildPrio(i)
n = n.children[i]
continue walk
}
}
// Otherwise insert it
if c != ':' && c != '*' {// []byte for proper unicode char conversion, see #65
n.indices += string([]byte{c})
child := &node{maxParams: numParams,}
n.children = append(n.children, child)
n.incrementChildPrio(len(n.indices) - 1)
n = child
}
n.insertChild(numParams, path, fullPath, handlers)
return
} else if i == len(path) {
if n.handlers != nil {panic("handlers are already registered for path'" + fullPath + "'")
}
n.handlers = handlers
}
return
}
} else { // 节点为空，直接添加直接添加路由
n.insertChild(numParams, path, fullPath, handlers)
n.nType = root
}
}
// 添加节点函数 主要处理包含参数节点
func (n *node) insertChild(numParams uint8, path string, fullPath string, handlers HandlersChain) {
var offset int // already handled bytes of the path
// 循环查找前缀为 '：' 或者 '*'
for i, max := 0, len(path); numParams > 0; i++ {c := path[i]
if c != ':' && c != '*' {continue}
// 判断在 * 参数之后不能再有 * 或者: 否则则报错 除非到了下一个 /
end := i + 1
for end < max && path[end] != '/' {switch path[end] {
// the wildcard name must not contain ':' and '*'
case ':', '*':
panic("only one wildcard per path segment is allowed, has:'" +
path[i:] + "'in path'" + fullPath + "'")
default:
end++
}
}
// 检查这个节点是否存在子节点，如果我们在这里插入通配符，子节点将是不可访问的
if len(n.children) > 0 {panic("wildcard route'" + path[i:end] +
"'conflicts with existing children in path'" + fullPath + "'")
}
// check if the wildcard has a name
if end-i < 2 {panic("wildcards must be named with a non-empty name in path'" + fullPath + "'")
}
// 参数类型 相当于注册路由时候带有:
if c == ':' {
// split path at the beginning of the wildcard
if i > 0 {n.path = path[offset:i]
offset = i
}
child := &node{
nType: param,
maxParams: numParams,
}
n.children = []*node{child}
n.wildChild = true
n = child
n.priority++
numParams--
if end < max {n.path = path[offset:end]
offset = end
child := &node{
maxParams: numParams,
priority: 1,
}
n.children = []*node{child}
n = child
}
} else {
// 如果是通配符 *
if end != max || numParams > 1 {panic("catch-all routes are only allowed at the end of the path in path'" + fullPath + "'")
}
if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {panic("catch-all conflicts with existing handle for the path segment root in path'" + fullPath + "'")
}
// currently fixed width 1 for '/'
i--
if path[i] != '/' {panic("no / before catch-all in path'" + fullPath + "'")
}
n.path = path[offset:i]
// first node: catchAll node with empty path
child := &node{
wildChild: true,
nType: catchAll,
maxParams: 1,
}
n.children = []*node{child}
n.indices = string(path[i])
n = child
n.priority++
// second node: node holding the variable
child = &node{path: path[i:],
nType: catchAll,
maxParams: 1,
handlers: handlers,
priority: 1,
}
n.children = []*node{child}
return
}
}
// 插入路由 如果不包含参数节点 offset 为 0
n.path = path[offset:]
n.handlers = handlers
}最后我们要看下根据 path 获取 router 的方法 getRouter。这个方法还是比较简单的，注释基本也能明白。
// 根据 path 查找路由的方法
func (n *node) getValue(path string, po Params, unescape bool) (handlers HandlersChain, p Params, tsr bool) {
p = po
walk:
for {if len(path) > len(n.path) {if path[:len(n.path)] == n.path {path = path[len(n.path):]
// 判断如果不是参数节点
// 那 path 的第一个字符 循环对比 indices 中的每个字符查找到子节点
if !n.wildChild {c := path[0]
for i := 0; i < len(n.indices); i++ {if c == n.indices[i] {n = n.children[i]
continue walk
}
}
tsr = path == "/" && n.handlers != nil
return
}
// handle wildcard child
n = n.children[0]
switch n.nType {
case param:
// 如果是普通 ':' 节点, 那么找到 / 或者 path end, 获得参数
end := 0
for end < len(path) && path[end] != '/' {end++}
// save param value
if cap(p) < int(n.maxParams) {p = make(Params, 0, n.maxParams)
}
i := len(p)
p = p[:i+1] // expand slice within preallocated capacity
p[i].Key = n.path[1:]
val := path[:end]
if unescape {
var err error
if p[i].Value, err = url.QueryUnescape(val); err != nil {p[i].Value = val // fallback, in case of error
}
} else {p[i].Value = val
}
// 如果参数还没处理完, 继续 walk
if end < len(path) {if len(n.children) > 0 {path = path[end:]
n = n.children[0]
continue walk
}
// ... but we can't
tsr = len(path) == end+1
return
}
// 否则获得 handle 返回就 OK
if handlers = n.handlers; handlers != nil {return}
if len(n.children) == 1 {
// No handle found. Check if a handle for this path + a
// trailing slash exists for TSR recommendation
n = n.children[0]
tsr = n.path == "/" && n.handlers != nil
}
return
case catchAll:
// * 匹配所有参数
if cap(p) < int(n.maxParams) {p = make(Params, 0, n.maxParams)
}
i := len(p)
p = p[:i+1] // expand slice within preallocated capacity
p[i].Key = n.path[2:]
if unescape {
var err error
if p[i].Value, err = url.QueryUnescape(path); err != nil {p[i].Value = path // fallback, in case of error
}
} else {p[i].Value = path
}
handlers = n.handlers
return
default:
panic("invalid node type")
}
}
} else if path == n.path {
// We should have reached the node containing the handle.
// Check if this node has a handle registered.
if handlers = n.handlers; handlers != nil {return}
if path == "/" && n.wildChild && n.nType != root {
tsr = true
return
}
// No handle found. Check if a handle for this path + a
// trailing slash exists for trailing slash recommendation
for i := 0; i < len(n.indices); i++ {if n.indices[i] == '/' {n = n.children[i]
tsr = (len(n.path) == 1 && n.handlers != nil) ||
(n.nType == catchAll && n.children[0].handlers != nil)
return
}
}
return
}
// Nothing found. We can recommend to redirect to the same URL with an
// extra trailing slash if a leaf exists for that path
tsr = (path == "/") ||
(len(n.path) == len(path)+1 && n.path[len(path)] == '/' &&
path == n.path[:len(n.path)-1] && n.handlers != nil)
return
}
}总结
Gin 的路由是它的特色，其实就是因为他的存储结构。基数树的存储结构可以很快的查询到对应路由并且执行到 handler。避免了每次请求循环所有路由的逻辑，提升了 Gin 整体的性能。试想如果一个大型项目中 GET 路由有 100 个，如果每次请求都去循环 100 次查找性能会很差，如果使用基数树的存储方式可能只需要经过几次的查询。
Gin 路由代码很长，其中大部分是处理带有参数的节点的逻辑。下一次的学习中，还是老规矩，自己模仿着写一个基数树存储结构的路由查找逻辑。去除掉那些参数逻辑只留下主要核心逻辑。