# 路由内部实现：基树
## 路由的内部实现
前面我们把route接口层面的调用都过了一遍，gin的代码调用还是很简单直接的。
> 程序 = 数据结构 + 算法
gin的核心结构体叫 `Engine` ，那引擎到底在哪呢？我想就是它的路由实现。接下来我们去一窥究竟。
### 基树
[基树维基百科](https://en.wikipedia.org/wiki/Radix_tree) 详细介绍了基树这种数据结构。它是gin的router的底层数据结构。
### 具体实现
```
node的数据结构：
// tree.go:88
type node struct {
// 相对路径
path string
// 索引
indices string
// 子节点
children []*node
// 处理者列表
handlers HandlersChain
priority uint32
// 结点类型：static, root, param, catchAll
nType nodeType
// 最多的参数个数
maxParams uint8
// 是否是通配符(:param_name | *param_name)
wildChild bool
}
```
#### 基树的构建
构建的过程其实是不断寻找最长前缀的过程。
我们抛开具体的代码，从数据结构变化来看具体实现：
最初的数据时：engine.roots = nil
step1: engine.Use(f1)
step2：添加{method: POST, path: /p1, handler:f2}
```
/p1
node_/p1 = {
path:"/p1"
indices:""
handlers:[f1, f2]
priority:1
nType:root
maxParams:0
wildChild:false
}
engine.roots = [{
method: POST,
root: node_/p1
}]
```
step3：添加{method: POST, path: /p, handler:f3}
```
/p
/p1
node_/p = {
path:"/p"
indices:"1"
handlers:[f1, f3]
priority:2
nType:root
maxParams:0
wildChild:false
children: [
{
path:"1"
indices:""
children:[]
handlers: [f1, f2]
priority:1
nType:static
maxParams:0
wildChild:false
}
]
}
engine.roots = [{
method: POST,
root: node_/p
}]
```
step4：添加{method: POST, path: /, handler:f4}
```
/
/p
/p1
node_/ = {
path:"/"
indices:"p"
handlers:[f1, f4]
priority:3
nType:root
maxParams:0
wildChild:false
children:[
{
path:"p"
indices:"1"
handlers:[f1, f3]
priority:2
nType:static
maxParams:0
wildChild:false
children:[
{
path:"1"
indices:""
children:[]
handlers:[f1, f2]
priority:1
nType:static
maxParams:0
wildChild:false
}
]
}
]
}
engine.roots = [{
method: POST,
root: node_/
}]
```
step5：添加{method: POST, path: /p1/p34, handler:f5}
```
/
/p
/p1
/p1/p34
node_/ = {
path:"/"
indices:"p"
handlers:[f1, f4]
priority:4
nType:root
maxParams:0
wildChild:false
children:[
{
path:"p"
indices:"1"
handlers:[f1, f3]
priority:3
nType:static
maxParams:0
wildChild:false
children:[
{
path:"1"
indices:""
handlers:[f1, f2]
priority:2
nType:static
maxParams:0
wildChild:false
children:[
{
path:"/p34"
indices:""
handlers:[f1, f5]
priority:1
nType:static
maxParams:0
wildChild:false
children:[]
}
]
}
]
}
]
}
engine.roots = [{
method: POST,
root: node_/
}]
```
step6：添加{method: POST, path: /p12, handler:f6}
```
/
/p
/p1
/p1/p34
/p12
node_/ = {
path:"/"
indices:"p"
handlers:[f1, f4]
priority:5
nType:root
maxParams:0
wildChild:false
children:[
{
path:"p"
indices:"1"
handlers:[f1, f3]
priority:4
nType:static
maxParams:0
wildChild:false
children:[
{
path:"1"
indices:"/2"
handlers:[f1, f2]
priority:3
nType:static
maxParams:0
wildChild:false
children:[
{
path:"/p34"
indices:""
handlers:[f1, f5]
priority:1
nType:static
maxParams:0
wildChild:false
children:[]
}
{
path:"2"
indices:""
handlers:[f1, f6]
priority:1
nType:static
maxParams:0
wildChild:false
children:[]
}
]
}
]
}
]
}
```
step7：添加{method: POST, path: /p12/p56, handler:f7}
```
/
/p
/p1
/p1/p34
/p12
/p12/p56
node_/ = {
path:"/"
indices:"p"
handlers:[f1, f4]
priority:5 + 1
nType:root
maxParams:0
wildChild:false
children:[
{
path:"p"
indices:"1"
handlers:[f1, f3]
priority:4 + 1
nType:static
maxParams:0
wildChild:false
children:[
{
path:"1"
indices:"2/"
handlers:[f1, f2]
priority:3 + 1
nType:static
maxParams:0
wildChild:false
children:[
{
path:"2"
indices:""
handlers:[f1, f6]
priority:2
nType:static
maxParams:0
wildChild:false
children:[
{
path:"/p56"
indices:""
handlers:[f1, f7]
priority:1
nType:static
maxParams:0
wildChild:false
children:[]
}
]
}
{
path:"/p34"
indices:""
handlers:[f1, f5]
priority:1
nType:static
maxParams:0
wildChild:false
children:[]
}
]
}
]
}
]
}
```
step8：添加{method: POST, path: /p12/p56/:id, handler:f8}
```
/
/p
/p1
/p1/p34
/p12
/p12/p56
/p12/p56/:id
node_/ = {
path:"/"
indices:"p"
handlers:[f1, f4]
priority:6 + 1
nType:root
maxParams:0 + 1
wildChild:false
children:[
{
path:"p"
indices:"1"
handlers:[f1, f3]
priority:5 + 1
nType:static
maxParams:1
wildChild:false
children:[
{
path:"1"
indices:"2/"
handlers:[f1, f2]
priority:4 + 1
nType:static
maxParams:1
wildChild:false
children:[
{
path:"2"
indices:""
handlers:[f1, f6]
priority:2 + 1
nType:static
maxParams:1
wildChild:false
children:[
{
path:"/p56"
indices:""
handlers:[f1, f7]
priority:1 + 1
nType:static
maxParams:1
wildChild:false
children:[
{
path:"/"
indices:""
handlers:[]
priority:1
nType:static
maxParams:1
wildChild:false
children:[
{
path:":id"
indices:""
handlers:[f1, f8]
priority:1
nType:param
maxParams:1
wildChild:false
children:[]
}
]
}
]
}
]
}
{
path:"/p34"
indices:""
handlers:[f1, f5]
priority:1
nType:static
maxParams:0
wildChild:false
children:[]
}
]
}
]
}
]
}
```
step9：添加{method: POST, path: /p12/p56/:id/p78, handler:f9}
```
/
/p
/p1
/p1/p34
/p12
/p12/p56
/p12/p56/:id
node_/ = {
path:"/"
indices:"p"
handlers:[f1, f4]
priority:7 + 1
nType:root
maxParams:0 + 1
wildChild:false
children:[
{
path:"p"
indices:"1"
handlers:[f1, f3]
priority:6 + 1
nType:static
maxParams:1
wildChild:false
children:[
{
path:"1"
indices:"2/"
handlers:[f1, f2]
priority:5 + 1
nType:static
maxParams:1
wildChild:false
children:[
{
path:"2"
indices:"/"
handlers:[f1, f6]
priority:3 + 1
nType:static
maxParams:1
wildChild:false
children:[
{
path:"/p56"
indices:""
handlers:[f1, f7]
priority:2 + 1
nType:static
maxParams:1
wildChild:false
children:[
{
path:"/"
indices:""
handlers:[]
priority:1 + 1
nType:static
maxParams:1
wildChild:true
children:[
{
path:":id"
indices:""
handlers:[f1, f8]
priority:1 + 1
nType:param
maxParams:1
wildChild:false
children:[
{
path:"/p78"
indices:""
handlers:[f1, f9]
priority:1
nType:static
maxParams:0
wildChild:false
children:[]
}
]
}
]
}
]
}
]
}
{
path:"/p34"
indices:""
handlers:[f1, f5]
priority:1
nType:static
maxParams:0
wildChild:false
children:[]
}
]
}
]
}
]
}
```
#### 基树的查找
基数的查找不抠细节的话其实就是从根节点一直 匹配当前节点和匹配孩子节点，直到找到匹配的节点，返回handlers。
代码在： tree.go:365
