基数树（radix），也称压缩前缀树，前缀树的查找速度是跟 树的深度有关的。 并且从在单一分支的情况，且对单一超长的 word 或者是比较稀疏的单词的时候，存储很费力不讨好，会导致树总是只有单个分支，大大提高树的深度 和 存储空间。

    应对大量的路由匹配， radix 树可以提高你应对大量匹配的能力。


    我们以 gin 的路由匹配我例：
    image.pngimage.png

    CODE
    注：以下代码只实现了一个简陋的radix，包含了该算法的核心思想

    1. package main
    3. import (
    4.     "fmt"
    5. )
    7. type Handlers []func()
    9. type node struct {
    10.     // 保存这个节点上的URL路径
    11.     path string
    12.     // 和children[]对应, 保存的是分裂的分支的第一个字符
    13.     // 例如search和support, 那么s节点的indices对应的"eu"
    14.     // 代表有两个分支, 分支的首字母分别是e和u
    15.     indices  string
    16.     children []*node
    17.     handlers Handlers
    18. }
    20. func NewNode() *node {
    21.     return &node{path: "/"}
    22. }
    24. func (n *node) addRoute(path string, handlers Handlers) {
    25.     if len(n.children) < 1 {
    26.         n.insertChild(path, handlers, 0)
    27.         return
    28.     }
    30. loop:
    31.     for {
    32.         //找到前缀相等的部分
    33.         i := 0
    34.         max := min(len(path), len(n.path))
    35.         for max > i && path[i] == n.path[i] {
    36.             i++
    37.         }
    39.         //判断是否有前缀相同，如果有相同的则把目前这个节点提取出来作为子节点
    40.         //再把相同前缀的path部分作为 父节点
    41.         //比如n.path = romaned 现在新增路由的path = romanus 相同前缀为 roman
    42.         //步骤为：
    43.         //1. 提取ed 新建一个child节点 把原来n的属性都复制过去
    44.         //2. 把原来的n的path改为相同前缀：roman， 为indices添加 子节点的第一个字符:e
    45.         // 注意：i == 0 时，没有相同的前缀，不需要重新更改节点
    46.         // n.path != "/" 这个条件可以不用，但写上更直观些
    47.         if i < len(n.path) && i > 0 && n.path != "/" {
    48.             //新建node
    49.             child := node{
    50.                 path:     n.path[i:],
    51.                 indices:  n.indices,
    52.                 handlers: n.handlers,
    53.                 children: n.children,
    54.             }
    56.             n.children = []*node{&child}
    57.             n.indices = string(n.path[i])
    58.             n.path = path[:i]
    59.             n.handlers = handlers
    60.         }
    62.         //原先的节点n现在已经分成2个节点了 结构为：
    63.         //roman 父节点
    64.         //    ed    子节点[0]
    65.         //那么现在需要把传入的路由添加到这个父节点中
    66.         //最终结构为
    67.         //roman 父节点
    68.         //    ed 子节点[0]
    69.         //    us 子节点[1]
    70.         // 其中还有一些情况需要自调用 相当于递归 举例说明：
    71.         //roman
    72.         //    ed
    73.         //    uie
    74.         //当判断父节点n 本来就有一个uie子节点 这时候uie和us 又有相同前缀u 这个时候需要把这个u再次提取出来作为父节点 所以需要递归调用walk
    75.         //最终结果为 三层结构
    76.         //roman
    77.         //    ed
    78.         //    u
    79.         //        ie
    80.         //        s
    81.         //还有一种情况是如果是带有参数的路由 则也会再次调用walk
    83.         // 如果 i>=len(path)，说明 这个path 被之前的path包含了，上面的逻辑已经做了处理
    84.         if i < len(path) {
    85.             c := path[i] // 按上面的例子，这里的c(第一个不相同的字符) 为 'u'
    86.             // 按上面的注释
    87.             // 最终两层时，n.indices 为 'e'
    88.             // 最终三层时，n.indices 为 'eu'
    89.             for index := 0; index < len(n.indices); index++ {
    90.                 if c == n.indices[index] {
    91.                     n = n.children[index]
    92.                     path = path[i:]
    93.                     continue loop
    94.                 }
    95.             }
    97.             //把新请求的path加入到router中
    98.             n.insertChild(path, handlers, i)
    99.             return
    100.         }
    101.         return
    102.     }
    103. }
    105. func (n *node) insertChild(fullPath string, handlers Handlers, index int) {
    106.     child := node{}
    107.     child.handlers = handlers
    108.     child.indices = ""
    109.     child.path = fullPath[index:]
    110.     n.indices += string(fullPath[index])
    111.     n.children = append(n.children, &child)
    112. }
    114. func min(a, b int) int {
    115.     if a > b {
    116.         return b
    117.     }
    119.     return a
    120. }
    122. func (n *node) getValue(path string) (handlers Handlers) {
    123.     index := 1
    124. walk:
    125.     for {
    126.         if len(path) > len(n.path) {
    127.             // 这个边界要注意，因为除了根节点，其它节点不能以"/"开头
    128.             if n.path != "/" {
    129.                 path = path[len(n.path):]
    130.             }
    131.             c := path[0]
    132.             for i := 0; i < len(n.indices); i++ {
    133.                 if c == n.indices[i] {
    134.                     n = n.children[i]
    135.                     index++
    136.                     goto walk
    137.                 }
    138.             }
    139.         } else if path == n.path {
    140.             return n.handlers
    141.         } else {
    142.             return nil
    143.         }
    144.     }
    145. }
    147. func main() {
    148.     node := NewNode()
    150.     node.addRoute("romaned", Handlers{func() {
    151.         fmt.Println("romaned")
    152.     }})
    154.     node.addRoute("romanus", Handlers{func() {
    155.         fmt.Println("romanus")
    156.     }})
    158.     node.addRoute("romanuie", Handlers{func() {
    159.         fmt.Println("romanuie")
    160.     }})
    162.     node.getValue("romaned")[0]()
    163.     node.getValue("romanus")[0]()
    164.     node.getValue("romanuie")[0]()
    165. }