前缀树算法实现路由匹配原理解析：Go 实现

路由功能是 web 框架中一个很重要的功能，它将不同的请求转发给不同的函数(handler)处理，很容易能想到，我们可以用一个字典保存它们之间的对应关系，字典的 key 存放 path，value 存放 handler。当一个请求过来后，使用 routers.get(path, None) 就可以找到对应的 handler。

利用字典实现路由可以参考我的这篇文章：动手实现 web 框架^[1] 。

使用字典有一个问题，不支持动态路由。如果路由像这样呢？

/hello/:name/profile

name 前面是通配符: ，表示这是个动态的值。一个解决办法是使用前缀树 trie。

前缀树

leetcode 中有这个算法，点这里^[2] 查看。

前缀树前缀树，首先是一棵树。不同的是树中一个节点的所有子孙都有相同的前缀。前缀树将单词中的每个字母依次插入树中，插入前首先确认该单词是否存在，不存在才创建新节点，如果一个单词已经全部插入，则将末尾单词设置为标志位。

type Node struct {
    isWord bool // 是否是单词结尾
    next   map[string]*Node // 子节点
}

type Trie struct {
    root *Node
}

以单词 leetcode，leetd 和 code 为例，首先一次插入 leetcode 中的每个单词，然后插入 leetd 的时候，leet 在树中已经存在，跳过往下，现在要插入字母 d，不存在，所以新建节点插入树中，并将该节点的 isWord 置位 true，表明到了单词末尾。

最终插入结果为：

func (this *Trie) Insert(word string) {
    cur := this.root
    for _, w := range []rune(word) {
        c := string(w)
        if cur.next[c] == nil {
            cur.next[c] = &Node{next: make(map[string]*Node)}
        }
        cur = cur.next[c]
    }
    cur.isWord = true
}

那么，当我们要搜索单词 leetd 的时候，从根节点开始查找，如果找到某条路径是 leetd，并且末尾的 d 是单词标志位，则表示搜索成功。

func (this *Trie) Search(word string) bool {
    cur := this.root
    for _, w := range []rune(word) {
        c := string(w)
        if cur.next[c] == nil {
            return false
        }
        cur = cur.next[c]
    }
    return cur.isWord
}

明白了前缀树的原理，我们来看看路由匹配是如何利用前缀树来实现的。

路由前缀树

go 语言中 gin 框架的路由实现就是利用前缀树，可以看看它的源代码是如何实现的。

考虑一下，路由或者说路径的特点，是以 / 分隔的单词组成的，那我们将 / 的每一部分挂靠在前缀树上就可以了。如下图所示：

还有一点需要考虑，我们在用 web 框架定义路由的时候，常见的做法是根据不同的 HTTP 方法来定义。比如：

// 以go语言gin框架为例
g := gin.New()
g.GET("/hello", Hello)
g.POST("/form", Form)

对于同一个路径，可能有多个方法支持。所以我们要以不同 HTTP 方法为树根创建前缀树。当一个 GET 请求过来的时候，就从 GET 树上搜索，POST 请求就从 POST 树上搜索。

除了为不同的 HTTP 方法定义树之外，还要给那些是通配符的节点增加一个标志位。所以，我们的路由前缀树结构看起来像这样：

type node struct {
    path     string           // 路由路径
    part     string           // 路由中由'/'分隔的部分
    children map[string]*node // 子节点
    isWild   bool             // 是否是通配符节点
}

type router struct {
    root  map[string]*node       // 路由树根节点
    route map[string]HandlerFunc // 路由处理handler
}

依照上面的前缀树算法的实现，照葫芦画瓢，我们可以写出插入路由和搜索路由的方法：

// addRoute 绑定路由到handler
func (r *router) addRoute(method, path string, handler HandlerFunc) {
    parts := parsePath(path)
    if _, ok := r.root[method]; !ok {
        r.root[method] = &node{children: make(map[string]*node)}
    }
    root := r.root[method]
    key := method + "-" + path
    // 将parts插入到路由树
    for _, part := range parts {
        if root.children[part] == nil {
            root.children[part] = &node{
                part:     part,
                children: make(map[string]*node),
                isWild:   part[0] == ':' || part[0] == '*'}
        }
        root = root.children[part]
    }
    root.path = path
    // 绑定路由和handler
    r.route[key] = handler
}

// getRoute 获取路由树节点以及路由变量
func (r *router) getRoute(method, path string) (node *node, params map[string]string) {
    params = map[string]string{}
    searchParts := parsePath(path)

    // get method trie
    var ok bool
    if node, ok = r.root[method]; !ok {
        return nil, nil
    }

    // 在该方法的路由树上查找该路径
    for i, part := range searchParts {
        var temp string
        // 查找child是否等于part
        for _, child := range node.children {
            if child.part == part || child.isWild {
                // 添加参数
                if child.part[0] == '*' {
                    params[child.part[1:]] = strings.Join(searchParts[i:], "/")
                }
                if child.part[0] == ':' {
                    params[child.part[1:]] = part
                }
                temp = child.part
            }

        }
        // 遇到通配符*，直接返回
        if temp[0] == '*' {
            return node.children[temp], params
        }
        node = node.children[temp]

    }

    return

}

上面的代码是我自己实现的一个 web 框架 **gaga**^[3] 中路由前缀树相关的代码，有需要的可以去看看源代码。另外，欢迎star 呀。

其中的 addRoute 用来将路由插入到对应 method 的路由树中，如果节点是通配符，将其设置为 isWild ， 同时绑定路由和 handler 方法。

getRoute 方法首先查找路由方法对应的路由前缀树，然后在树中查找是否存在该路径。

总结

前缀树 trie 算法不光可以用在路由的实现上，搜索引擎中自动补全的实现，拼写检查等等都是用 trie 实现的。trie 树查找的时间和空间复杂度都是线性的，效率很高，很适合路由这种场景使用。

路由的实现上，go 语言中 httpRouter 这个库除了使用前缀树之外，还加入了优先级，有兴趣的可以看看它的源码了解下。

作者：鸟石

原文链接：https://segmentfault.com/a/1190000021657573

参考资料