Gin路由树构建与查找算法

Gin使用压缩前缀树（Radix Tree）实现高效路由，理解其算法有助于优化路由设计。

Radix树基础

节点结构

type node struct {
    path      string      // 节点路径
    indices   string      // 子节点首字符索引
    children  []*node     // 子节点
    handlers  HandlersChain // 处理函数
    priority  uint32      // 优先级（访问频率）
    nType     uint8       // 节点类型
    maxParams uint8       // 最大参数数量
    wildChild bool        // 是否有通配子节点
}

// 节点类型常量
const (
    static nodeType = iota  // 静态节点
    root                    // 根节点
    param                   // 参数节点 :param
    catchAll                // 通配节点 *filepath
)

树结构示意

注册路由：
GET /users
GET /users/:id
GET /users/profile
GET /articles/:id

Radix树结构：
root
└── users (handlers)
    ├── /profile (handlers)
    └── /:id (handlers)

root
└── articles/
    └── :id (handlers)

路由添加算法

核心addRoute方法

func (n *node) addRoute(path string, handlers HandlersChain) {
    fullPath := path

    // 空树直接设置
    if n.path == "" && n.indices == "" {
        n.insertChild(path, fullPath, handlers)
        return
    }

Walk:
    for {
        // 找最长公共前缀
        i := longestCommonPrefix(path, n.path)

        // 需要分割节点
        if i < len(n.path) {
            child := node{
                path:     n.path[i:],
                indices:  n.indices,
                children: n.children,
                handlers: n.handlers,
                priority: n.priority,
            }
            n.path = path[:i]
            n.indices = string([]byte{child.path[0]})
            n.children = []*node{&child}
            n.handlers = nil
        }

        // 添加新路径
        if i < len(path) {
            path = path[i:]

            // 查找匹配子节点
            for i, idx := range []byte(n.indices) {
                if idx == path[0] {
                    n = n.children[i]
                    continue Walk
                }
            }

            // 创建新子节点
            n.insertChild(path, fullPath, handlers)
            return
        }

        // 路径已存在
        n.handlers = handlers
        return
    }
}

节点分割示例

已有路由: /hello
新增路由: /help

步骤1: 找公共前缀 "hel"
步骤2: 分割节点
  /hello → /hel → llo (子节点)
步骤3: 添加新分支
  /hel → llo
       → p

最终树:
root
└── hel
    ├── lo (handlers for /hello)
    └── p  (handlers for /help)

通配符处理

参数节点插入

func (n *node) insertChild(path, fullPath string, handlers HandlersChain) {
    for {
        // 查找通配符
        wildcard, i, valid := findWildcard(path)

        if !valid {
            panic("invalid wildcard")
        }

        if wildcard == "" {
            break
        }

        // 参数类型 :param
        if wildcard[0] == ':' {
            // 创建参数节点
            n.wildChild = true
            child := &node{
                nType: param,
                path:  wildcard,
            }
            n.children = append(n.children, child)
            n = child
        }

        // 通配类型 *filepath
        if wildcard[0] == '*' {
            child := &node{
                nType: catchAll,
                path:  wildcard,
            }
            n.children = append(n.children, child)
            n = child
        }

        path = path[i+1:]
    }

    n.handlers = handlers
}

路由查找算法

getValue核心方法

func (n *node) getValue(path string, params *Params, unescape bool) (value nodeValue) {
    value = nodeValue{}

Walk:
    for {
        prefix := n.path

        // 完全匹配
        if path == prefix {
            value.handlers = n.handlers
            return
        }

        // 前缀匹配
        if len(path) > len(prefix) && path[:len(prefix)] == prefix {
            path = path[len(prefix):]

            // 静态子节点匹配
            if !n.wildChild {
                idxc := path[0]
                for i, c := range []byte(n.indices) {
                    if c == idxc {
                        n = n.children[i]
                        continue Walk
                    }
                }

                // 无匹配
                return
            }

            // 通配子节点处理
            n = n.children[0]

            switch n.nType {
            case param:
                // 提取参数直到 /
                end := 0
                for end < len(path) && path[end] != '/' {
                    end++
                }

                *params = append(*params, Param{
                    Key:   n.path[1:], // 去掉冒号
                    Value: path[:end],
                })

                if end < len(path) {
                    path = path[end:]
                    continue Walk
                }

                value.handlers = n.handlers
                return

            case catchAll:
                // 匹配剩余所有路径
                *params = append(*params, Param{
                    Key:   n.path[1:], // 去掉星号
                    Value: path,
                })
                value.handlers = n.handlers
                return
            }
        }
    }
}

查找性能分析

注意：路由树构建时按优先级排序，高频路由会被优先匹配。

要点总结

• Radix树通过公共前缀压缩节点，减少内存占用
• 节点分割发生在公共前缀不匹配时
• 参数节点(:param)和通配节点(*filepath)特殊处理
• 查找时间复杂度O(k)，k为路径长度
• priority字段用于记录访问频率，优化热路径