gin框架httprouter路由原理

一、前缀树和基数树（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 对下级节点的查找进行了优化，简单来说就是把当前节点的下级节点的首字母维护在本身，匹配时先进行索引的查找。

有疑问加站长微信联系（非本文作者）