一、前缀树和基数树（radix tree）的区别：
trie又叫前缀树，是一个多叉树，广泛应用于字符串搜索，每个树节点存储一个字符，从根节点到任意一个叶子结点串起来就是一个字符串；radix tree是优化之后的前缀树，对空间进一步压缩。
下图左侧是字符串 sex,seed,sleep,son 四个字段串的Trie数据结构表示. 可用看到sleep这个字符串需要5个节点表示. 其实e后面只跟一个p, 也就是只有一个子节点, 是完全可以和父节点压缩合并的. 右侧是优化后的数据结构, 节省了空间,同时也提高了查询效率(左边字符串sleep查询需要5步, 右边只需要3步), 这就是radix tree.
二、gin框架路由原理
httprouter是一个高性能路由分发器，它负责将不同方法的多个路径分别注册到各个handle函数，当收到请求时，负责快速查找请求的路径是否有相对应的处理函数，并且进行下一步业务逻辑处理。golang的gin框架采用了httprouter进行路由匹配，httprouter 是通过radix tree来进行高效的路径查找；同时路径还支持两种通配符匹配。
httprouter会对每种http方法（post、get等）都会生成一棵基数树，其中树节点node结构如下：
type nodestruct {
path string //该节点对应的path
indices string //子节点path的第一个byte的集合
wildChild bool //是否通配符
nType nodeType //节点类型
priority uint32
children []*node //子节点
handlers HandlersChain //handle如果不为nil，则说明是一个路径字符串的终点!!!
fullPath string
}
type nodeType uint8
const (
static nodeType =iota // default 普通节点
root //根节点
param //参数节点 /user/{id}，id 就是一个参数节点
catchAll //通配符
)
gin注册路由过程：
如下左边是/sex,/sleep,/son的内部呈现, 右边是插入/seed 后内部的呈现:
gin路由
简单的来说每一个注册的 url 都会通过 / 切分为 n 个树节点（httprouter 会有一些区别，会存在根分裂），然后挂到相应 method 树上去，所以业务中有几种不同的 method 接口，就会产生对应的前缀树。在 httprouter 中，节点被分为 4 种类型：
-- static - 静态节点，/user /api 这种
-- root - 根结点
-- param - 参数节点 /user/{id}，id 就是一个参数节点
-- catchAll - 通配符
其实整个匹配的过程也比较简单，通过对应的 method 拿到前缀树，然后开始进行一个广度优先的匹配。
这里值得学习的一点是，httprouter 对下级节点的查找进行了优化，简单来说就是把当前节点的下级节点的首字母维护在本身，匹配时先进行索引的查找。
有疑问加站长微信联系（非本文作者）
