1 简介

本文分析 Trie 树 和 Radix 树，并实现示例，在 Web 框架（如 Gin、Fiber 等）的路由匹配中，Trie 树 和 Radix 树 都是常用的数据结构。它们都可以高效存储和匹配字符串路径，但在实现和性能上存在显著区别。

1. Trie 树（前缀树）

Trie 树是一种多叉树，用于快速查找字符串。它的每个节点代表一个字符，路径表示字符串。Trie 树可以高效地执行字符串匹配操作。

特点

每个节点表示字符串中的一个字符
节点层级表示字符串的前缀
查询时间复杂度为 O(m)，其中 m 为字符串长度
占用内存较多，因为每个节点都需要额外存储字符和子节点映射

实现原理

从根节点开始插入字符串
每个字符对应一个子节点
查询时沿着路径逐字符匹配

实现代码示例

    type TrieNode struct {
        children map[rune]*TrieNode
        isEnd    bool
    }

    type Trie struct {
        root *TrieNode
    }

    func NewTrie() *Trie {
        return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
    }

    func (t *Trie) Insert(word string) {
        node := t.root
        for _, ch := range word {
            if _, exists := node.children[ch]; !exists {
                node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
            }
            node = node.children[ch]
        }
        node.isEnd = true
    }

    func (t *Trie) Search(word string) bool {
        node := t.root
        for _, ch := range word {
            if _, exists := node.children[ch]; !exists {
                return false
            }
            node = node.children[ch]
        }
        return node.isEnd
    }

    func main() {
        trie := NewTrie()
        trie.Insert("/user")
        trie.Insert("/user/profile")

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

Trie 树优缺点

  优点  						缺点
  查询速度快   				内存占用大
  支持完整匹配和前缀匹配 		每层节点可能有多个子节点
  容易实现    				节点层级较多，查询路径较长

2. Radix 树（压缩前缀树）

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

特点

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

实现原理

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

实现代码示例

    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
    }

Radix 树优缺点

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

Trie 树 vs Radix 树

特性 Trie 树 Radix 树

内存占用 高 低
查询性能 较慢 更快
节点数量 多 少
实现难度 简单 复杂
路由匹配 ✅ 支持前缀匹配 ❌ 只支持完全匹配

3 为什么选择 Radix 树

Radix 树对路径存储更紧凑，减少内存占用
查询性能优于 Trie 树
大多数 HTTP 路径是全路径匹配，Radix 树更合适
Gin 中路由匹配的路径大部分具有公共前缀，如 /api/v1/user

4 小结

如果你需要快速匹配字符串且不在意内存占用，选择 Trie 树
如果你需要节省内存并追求更快的匹配速度，选择 Radix 树

高性能框架采用 Radix 树，主要是为了优化路由匹配性能。