1 简介

Radix 树是一种压缩版本的 Trie 树。它将公共前缀合并到一个节点，从而减少节点数量并提高查询效率。

许多web框架使用Radix 树（紧凑前缀树） 来匹配路由，类似于 Trie 树：

    静态路由（/user/profile）
    参数路由（/user/:id）
    通配符路由（/static/*filepath）

实现一个高效路由：

    type node struct {
        path     string
        handler  func(c *Context)
        children map[string]*node
    }

    func (n *node) insert(path string, handler func(c *Context)) {
        // 递归插入路由，构造 Radix 树
    }

    func (n *node) search(path string) *node {
        // 递归匹配路径
    }

关键点：Radix 树比线性匹配更快，避免大量 if-else 判断。

2 Radix（压缩前缀树）特点和概念

特点

将公共前缀合并，减少节点数量
查询时间复杂度仍然是 O(m)，但由于节点更少，查询更快
内存占用比 Trie 树小
常用于高效字符串存储，如路由匹配、IP 地址匹配等

实现原理

根节点表示空路径
每个节点保存字符串片段（公共前缀）
匹配时直接跳过公共前缀
节点路径不再是单字符，而是字符串片段

3 压缩前缀树Radix的示例

  type RadixNode struct {
      path     string
      children map[string]*RadixNode
      isEnd    bool
  }

  type RadixTree struct {
      root *RadixNode
  }

  func NewRadixTree() *RadixTree {
      return &RadixTree{root: &RadixNode{children: make(map[string]*RadixNode)}}
  }

  func (t *RadixTree) Insert(path string) {
      node := t.root

      for len(path) > 0 {
          match := false
          for key, child := range node.children {
              if strings.HasPrefix(path, key) {
                  match = true
                  path = path[len(key):]
                  node = child
                  break
              }
          }

          if !match {
              newNode := &RadixNode{path: path, children: make(map[string]*RadixNode)}
              node.children[path] = newNode
              node = newNode
              break
          }
      }
      node.isEnd = true
  }

  func (t *RadixTree) Search(path string) bool {
      node := t.root

      for len(path) > 0 {
          match := false
          for key, child := range node.children {
              if strings.HasPrefix(path, key) {
                  match = true
                  path = path[len(key):]
                  node = child
                  break
              }
          }

          if !match {
              return false
          }
      }
      return node.isEnd
  }

  func main() {
      tree := NewRadixTree()
      tree.Insert("/user")
      tree.Insert("/user/profile")

      fmt.Println(tree.Search("/user"))         // true
      fmt.Println(tree.Search("/user/profile")) // true
      fmt.Println(tree.Search("/admin"))        // false
  }

4 Radix 树优缺点

  优点  				缺点
  更快的查询速度 		实现复杂
  节点数量更少  		代码维护难度较高
  内存占用更低  		只能完全匹配，不支持前缀匹配

5 总结

要从零实现一个类似 Gin 的 Web 框架，需要：

高效的 Radix 树路由
轻量级 Context 管理
责任链中间件设计
支持路由分组
兼容 net/http
异常恢复机制

由此实现的web框架具有竞争力：比如gin性能接近 fasthttp，同时保持 net/http 兼容性，是 Go 语言 Web 框架中的最佳平衡点。