web框架中的快速路由Trie树

Trie 树简介

前缀树即Trie树。

https://en.wikipedia.org/wiki/Trie

下图为 b，abc，abd，bcd，abcd，efg，hii 这7个单词创建的trie树。

上图从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

除根节点外，每一个节点只包含一个字符。

每个节点的所有子节点包含的字符都不相同。

相比较map/hash字典实现的优点：利用字符串公共前缀来减少查询时间，减少无谓的字符串比较。

web框架中的快速路由Trie树

Trie树的结构非常适用于路由匹配。不同的web框架中的快速路由用到了不同的路由算法。Trie 树是其中简单的一种。

因为现在web框架中的路由往往加入了动态路由功能，即加入了参数提取，通配符，这些功能简化了用户的路由注册，但是增加了Trie树实现路由的复杂度。

比如定义了如下路由规则：

/:lang/doc
/:lang/tutorial
/:lang/intro
/about
/p/blog
/p/related

用前缀树来表示，是这样的：

动态路由具备以下两个功能。

参数匹配:。例如 /p/:lang/doc，可以匹配 /p/c/doc 和 /p/go/doc。
通配*。例如 /static/*filepath，可以匹配/static/fav.ico，也可以匹配/static/js/jQuery.js，这种模式常用于静态服务器，能够递归地匹配子路径。

golang实现

本次分析的源码放在 https://github.com/geektutu/7days-golang/blob/master/gee-web/day7-panic-recover/gee/router.go 和 https://github.com/geektutu/7days-golang/blob/master/gee-web/day7-panic-recover/gee/trie.go

首先要设计上图树的节点的结构体，用于存储一些节点信息：

路由算法主要包括路由注册和路由发现两个部分：

路由注册

路由注册的过程包括两部分：

检查路由根节点（以request method GET/POST/DELETE/PUT 区分几个路由根结点）是否存在，不存在则新建。并注册根节点信息。
递归注册根节点的所有子节点信息。

路由发现

路由注册的过程包括两部分：

一层层查找到最底层匹配的节点
获取动态路由（冒号，星号）匹配的参数

路由注册和路由发现的共通方法 func parsePattern() []string

该方法就是将入参完整的URL用斜杠分隔成字符串数组。同时考虑了两种情况：

连续斜杠的合并（适用于和路由组和URL拼接的重复情况）
通配符，但只支持一个，因为*通配符就是匹配当前和后面的所有URL，只需要考虑1个星的情况