Gin路由树与Radix树

Radix树（压缩前缀树）是Gin高效路由的核心，理解其原理有助于设计高效路由结构。

Radix树基础概念

与普通前缀树对比

普通前缀树存储 ["hello", "help", "held"]:
root
└── h
    └── e
        ├── l
        │   ├── l
        │   │   └── o  (hello)
        │   └── p      (help)
        └── l
            └── d      (held)

Radix树（压缩）存储相同数据：
root
└── hel
    ├── l → o (hello)
    └── d      (held)
        └── p  (help) -- 注：实际hel分支为 llo 和 p

核心优势

Gin 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                // 通配节点 *path
)

路由树结构示例

注册路由分析

r.GET("/users", handler1)
r.GET("/users/:id", handler2)
r.GET("/users/profile", handler3)
r.GET("/articles", handler4)
r.GET("/articles/:id/comments", handler5)

树结构

GET树:
root [path="", indices="ua"]
 ├── users [path="users", handlers=[handler1]]
 │    ├── / [path="/", indices=":p", wildChild=false]
 │    │    ├── :id [path=":id", nType=param, handlers=[handler2]]
 │    │    └── profile [path="profile", handlers=[handler3]]
 ├── articles [path="articles"]
 │    └── / [path="/", indices=":"]
 │    │    └── :id [path=":id", nType=param]
 │    │        └── /comments [path="/comments", handlers=[handler5]]

节点分裂算法

公共前缀分裂

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

分裂步骤:
1. 计算公共前缀长度: len("hel") = 3
2. 创建新节点保存原节点剩余部分
   原节点: path="hello" → path="hel", indices="lp"
   子节点: path="lo" (原hello的剩余)
   子节点: path="p"  (新增help的剩余)

代码实现

func (n *node) addRoute(path string, handlers HandlersChain) {
    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(child.path[0])
            n.children = []*node{child}
            n.handlers = nil
        }
    }
}

indices索引机制

索引作用

// indices存储子节点首字符，快速定位子节点
// 例如: indices="abc", children=[node_a, node_b, node_c]
// 查找时遍历indices匹配首字符，O(1)定位children数组位置

func findChild(n *node, c byte) *node {
    for i, idx := range []byte(n.indices) {
        if idx == c {
            return n.children[i]
        }
    }
    return nil
}

索引优化

// Gin按priority排序indices，热路径优先匹配
// 注册路由时调整children顺序
for i := len(n.children) - 1; i > 0; i-- {
    if n.children[i].priority > n.children[i-1].priority {
        n.children[i], n.children[i-1] = n.children[i-1], n.children[i]
        n.indices = swapIndices(n.indices, i, i-1)
    }
}

通配节点处理

参数节点 :param

// 参数节点特性:
// 1. wildChild = true
// 2. nType = param
// 3. 只有一个子节点
// 4. 匹配到下一个/为止

// 匹配: /users/:id
// 路径: /users/123
// 结果: Params{Key: "id", Value: "123"}

通配节点 *path

// 通配节点特性:
// 1. nType = catchAll
// 2. 匹配剩余全部路径
// 3. 必须在路径末尾

// 匹配: /files/*filepath
// 路径: /files/docs/readme.txt
// 结果: Params{Key: "filepath", Value: "docs/readme.txt"}

查找算法详解

func (n *node) getValue(path string) (value nodeValue) {
Walk:
    for {
        // 1. 前缀匹配检查
        prefix := n.path
        if len(path) < len(prefix) {
            return  // 路径不匹配
        }

        if path[:len(prefix)] != prefix {
            return  // 前缀不匹配
        }

        path = path[len(prefix):]  // 去除已匹配部分

        // 2. 完全匹配
        if len(path) == 0 {
            if n.handlers != nil {
                value.handlers = n.handlers
                return
            }
        }

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

        // 4. 通配子节点处理
        n = n.children[0]
        // 参数提取逻辑...
    }
}

性能特点

注意：避免过多参数路由，每个参数节点需要额外提取处理。

要点总结

• Radix树通过压缩公共前缀减少节点数量
• indices索引快速定位子节点，避免遍历
• priority排序使热路径优先匹配
• 参数节点(:param)匹配到下一个分隔符
• 通配节点(*path)匹配剩余全部路径
• 查找时间复杂度O(k)，与路由数量无关