trie，也称前缀树（prefix tree），是一种用来有效地存储和检索字符串的数据结构。这是一个用 ”Radix tree based routing, small memory foot print. No reflection. Predictable API performance.“ 中的单词生成的 trie：
type node struct {
children map[byte]*node
isWord bool
}
type Trie struct {
root *node
}
radix tree，也称为 radix trie，是一种经过空间优化的、紧凑的 trie。这是一个用 ”Radix tree based routing, small memory foot print. No reflection. Predictable API performance.“ 中的单词生成的 radix tree：
可见，radix tree 的结构更紧凑：结点存储字符或字符串，边上的字符用于索引子结点。公共前缀会被尽量地压缩，如果一个结点只有一个子结点，这两个结点会被合并为一个结点以节省空间。radix tree 的操作更加复杂。
数据结构基础
trie，也称前缀树（prefix tree），是一种用来有效地存储和检索字符串的数据结构。这是一个用 ”Radix tree based routing, small memory foot print. No reflection. Predictable API performance.“ 中的单词生成的 trie：
从逻辑上讲，trie 中的结点不存储字符或者字符串，相反，每条边存储一个字符，将从根结点到某一结点的路径上的所有字符串联起来就组成了该结点所表示的字符串，因此，根结点表示空字符串。一个 trie 可以用这样简单的数据结构表示：
radix tree，也称为 radix trie，是一种经过空间优化的、紧凑的 trie。这是一个用 ”Radix tree based routing, small memory foot print. No reflection. Predictable API performance.“ 中的单词生成的 radix tree：
可见，radix tree 的结构更紧凑：结点存储字符或字符串，边上的字符用于索引子结点。公共前缀会被尽量地压缩，如果一个结点只有一个子结点，这两个结点会被合并为一个结点以节省空间。radix tree 的操作更加复杂。
探索 Gin 的路由树
如果只是单纯看代码，很难理解 Gin 路由树的复杂规则，源码里
node结构体的字段甚至没有注释，如果不知道各个字段的含义，怎样理解源码？于是，我 fork 了 Gin 的代码，对 v1.9.1 做了一点修改，希望能可视化 Gin 的路由树，仓库在这里。这是一个生成的路由树结构，结果并不完美，但是可以帮助理解：路由树的逻辑结构
```go package main import ( gin "github.com/dushaoshuai/explore-gin-routes-tree" ) func doc(ctx *gin.Context) {} func docInstall(ctx *gin.Context) {} func docGetStart(ctx *gin.Context) {} func docCmd(ctx *gin.Context) {} func docUpload(ctx *gin.Context) {} func refMod(ctx *gin.Context) {} func refSpec(ctx *gin.Context) {} func userLogin(ctx *gin.Context) {} func userLogout(ctx *gin.Context) {} func companyLogin(ctx *gin.Context) {} func companyLogout(ctx *gin.Context) {} func main() { r := gin.Default() r.GET("/doc", doc) docGroup := r.Group("/doc") { docGroup.GET("/install", docInstall) docGroup.GET("/tutorial/getting-started", docGetStart) docGroup.GET("/cmd", docCmd) docGroup.POST("/upload", docUpload) } refGroup := r.Group("/ref") { refGroup.GET("/mod", refMod) refGroup.GET("/spec", refSpec) } r.POST("/user/login/:user", userLogin) r.POST("/user/logout/:user", userLogout) r.POST("/company/login/*company", companyLogin) r.POST("/company/logout/*company", companyLogout) r.Run() // default :8080 } ``` 运行上面这段代码后，访问 http://localhost:8080/debug-trees ： ``` ==================== GET ==================== nodeType: root priority: 7 wildChild: false path: / fullPath: / indices: dr │ │──d─┐ │ nodeType: static │ priority: 5 │ wildChild: false │ path: d │ fullPath: /d │ indices: oe │ │ │ │──o─┐ │ │ nodeType: static │ │ priority: 4 │ │ wildChild: false │ │ handlers: │ │ github.com/dushaoshuai/explore-gin-routes-tree.LoggerWithConfig.func1 │ │ github.com/dushaoshuai/explore-gin-routes-tree.CustomRecoveryWithWriter.func1 │ │ main.doc │ │ path: oc │ │ fullPath: /doc │ │ indices: / │ │ │ │ │ │──/─┐ │ │ │ nodeType: static │ │ │ priority: 3 │ │ │ wildChild: false │ │ │ path: / │ │ │ fullPath: /doc/ │ │ │ indices: itc │ │ │ │ │ │ │ │──i─┐ │ │ │ │ nodeType: static │ │ │ │ priority: 1 │ │ │ │ wildChild: false │ │ │ │ handlers: │ │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.LoggerWithConfig.func1 │ │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.CustomRecoveryWithWriter.func1 │ │ │ │ main.docInstall │ │ │ │ path: install │ │ │ │ fullPath: /doc/install │ │ │ │ │ │ │ │──t─┐ │ │ │ │ nodeType: static │ │ │ │ priority: 1 │ │ │ │ wildChild: false │ │ │ │ handlers: │ │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.LoggerWithConfig.func1 │ │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.CustomRecoveryWithWriter.func1 │ │ │ │ main.docGetStart │ │ │ │ path: tutorial/getting-started │ │ │ │ fullPath: /doc/tutorial/getting-started │ │ │ │ │ │ │ │──c─┐ │ │ │ │ nodeType: static │ │ │ │ priority: 1 │ │ │ │ wildChild: false │ │ │ │ handlers: │ │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.LoggerWithConfig.func1 │ │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.CustomRecoveryWithWriter.func1 │ │ │ │ main.docCmd │ │ │ │ path: cmd │ │ │ │ fullPath: /doc/cmd │ │ │ │──e─┐ │ │ nodeType: static │ │ priority: 1 │ │ wildChild: false │ │ handlers: │ │ github.com/dushaoshuai/explore-gin-routes-tree.LoggerWithConfig.func1 │ │ github.com/dushaoshuai/explore-gin-routes-tree.CustomRecoveryWithWriter.func1 │ │ github.com/dushaoshuai/explore-gin-routes-tree.Default.func1 │ │ path: ebug-trees │ │ fullPath: /debug-trees │ │──r─┐ │ nodeType: static │ priority: 2 │ wildChild: false │ path: ref/ │ fullPath: /ref/ │ indices: ms │ │ │ │──m─┐ │ │ nodeType: static │ │ priority: 1 │ │ wildChild: false │ │ handlers: │ │ github.com/dushaoshuai/explore-gin-routes-tree.LoggerWithConfig.func1 │ │ github.com/dushaoshuai/explore-gin-routes-tree.CustomRecoveryWithWriter.func1 │ │ main.refMod │ │ path: mod │ │ fullPath: /ref/mod │ │ │ │──s─┐ │ │ nodeType: static │ │ priority: 1 │ │ wildChild: false │ │ handlers: │ │ github.com/dushaoshuai/explore-gin-routes-tree.LoggerWithConfig.func1 │ │ github.com/dushaoshuai/explore-gin-routes-tree.CustomRecoveryWithWriter.func1 │ │ main.refSpec │ │ path: spec │ │ fullPath: /ref/spec ==================== POST ==================== nodeType: root priority: 5 wildChild: false path: / fullPath: / indices: ucd │ │──u─┐ │ nodeType: static │ priority: 2 │ wildChild: false │ path: user/log │ fullPath: /user/log │ indices: io │ │ │ │──i─┐ │ │ nodeType: static │ │ priority: 1 │ │ wildChild: true │ │ path: in/ │ │ fullPath: /user/login/:user │ │ │ │ │ │────┐ │ │ │ nodeType: param │ │ │ priority: 1 │ │ │ wildChild: false │ │ │ handlers: │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.LoggerWithConfig.func1 │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.CustomRecoveryWithWriter.func1 │ │ │ main.userLogin │ │ │ path: :user │ │ │ fullPath: /user/login/:user │ │ │ │──o─┐ │ │ nodeType: static │ │ priority: 1 │ │ wildChild: true │ │ path: out/ │ │ fullPath: /user/logout/:user │ │ │ │ │ │────┐ │ │ │ nodeType: param │ │ │ priority: 1 │ │ │ wildChild: false │ │ │ handlers: │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.LoggerWithConfig.func1 │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.CustomRecoveryWithWriter.func1 │ │ │ main.userLogout │ │ │ path: :user │ │ │ fullPath: /user/logout/:user │ │──c─┐ │ nodeType: static │ priority: 2 │ wildChild: false │ path: company/log │ fullPath: /company/log │ indices: io │ │ │ │──i─┐ │ │ nodeType: static │ │ priority: 1 │ │ wildChild: false │ │ path: in │ │ fullPath: /company/login/*company │ │ indices: / │ │ │ │ │ │──/─┐ │ │ │ nodeType: catchAll │ │ │ priority: 1 │ │ │ wildChild: true │ │ │ path: │ │ │ fullPath: /company/login/*company │ │ │ │ │ │ │ │────┐ │ │ │ │ nodeType: catchAll │ │ │ │ priority: 1 │ │ │ │ wildChild: false │ │ │ │ handlers: │ │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.LoggerWithConfig.func1 │ │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.CustomRecoveryWithWriter.func1 │ │ │ │ main.companyLogin │ │ │ │ path: /*company │ │ │ │ fullPath: /company/login/*company │ │ │ │──o─┐ │ │ nodeType: static │ │ priority: 1 │ │ wildChild: false │ │ path: out │ │ fullPath: /company/logout/*company │ │ indices: / │ │ │ │ │ │──/─┐ │ │ │ nodeType: catchAll │ │ │ priority: 1 │ │ │ wildChild: true │ │ │ path: │ │ │ fullPath: /company/logout/*company │ │ │ │ │ │ │ │────┐ │ │ │ │ nodeType: catchAll │ │ │ │ priority: 1 │ │ │ │ wildChild: false │ │ │ │ handlers: │ │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.LoggerWithConfig.func1 │ │ │ │ github.com/dushaoshuai/explore-gin-routes-tree.CustomRecoveryWithWriter.func1 │ │ │ │ main.companyLogout │ │ │ │ path: /*company │ │ │ │ fullPath: /company/logout/*company │ │──d─┐ │ nodeType: static │ priority: 1 │ wildChild: false │ handlers: │ github.com/dushaoshuai/explore-gin-routes-tree.LoggerWithConfig.func1 │ github.com/dushaoshuai/explore-gin-routes-tree.CustomRecoveryWithWriter.func1 │ main.docUpload │ path: doc/upload │ fullPath: /doc/upload ```Gin 路由树源码
好复杂呀，暂时先放下吧。代码需要多看几遍。
参见