目 录CONTENT

文章目录
Go

gin框架源码解析之Radix树介绍

Hello!你好!我是村望~!
2023-02-12 / 0 评论 / 0 点赞 / 134 阅读 / 1,188 字
温馨提示:
我不想探寻任何东西的意义,我只享受当下思考的快乐~

gin框架源码解析之Radix树介绍

简介

Gin 文档:

参考链接

** 对别人知识的整理!加上自己的理解!**

gin框架使用的是定制版本的httprouter,其路由的原理是大量使用公共前缀的树结构,它基本上是一个紧凑的Trie tree(或者只是Radix Tree)。具有公共前缀的节点也共享一个公共父节点。

Radix Tree

基数树(Radix Tree)又称为PAT位树(Patricia Trie or crit bit tree),是一种更节省空间的前缀树(Trie Tree)。

对于基数树的每个节点,如果该节点是唯一的子树的话,就和父节点合并。下图为一个基数树示例:

所有的节点都以 r 开头 那么 r 就成为了当前基树的根节点~然后看前三的 o 开头的作为下面的节点,其次是 m,但是 m 是 o 的唯一子节点!

所以 m 就和父节点 o 进行了合并,按照这个规律就形成了下面的基数树!

img

Radix Tree可以被认为是一棵简洁版的前缀树。我们注册路由的过程就是构造前缀树的过程,具有公共前缀的节点也共享一个公共父节点。

假设我们现在注册有以下路由信息:

r := gin.Default()

r.GET("/", func1)
r.GET("/search/", func2)
r.GET("/support/", func3)
r.GET("/blog/", func4)
r.GET("/blog/:post/", func5)
r.GET("/about-us/", func6)
r.GET("/about-us/team/", func7)
r.GET("/contact/", func8)

那么我们会得到一个GET方法对应的路由树,具体结构如下:

Priority   Path             Handle
9          \                *<1>
3          ├s               nil
2          |├earch\         *<2>
1          |└upport\        *<3>
2          ├blog\           *<4>
1          |    └:post      nil
1          |         └\     *<5>
2          ├about-us\       *<6>
1          |        └team\  *<7>
1          └contact\        *<8>
  • 上面最右边那一列每个*<数字>表示 Handle 处理函数的内存地址(一个指针)
  • 从根节点遍历到叶子节点我们就能得到完整的路由表。

例如:blog/:post其中:post只是实际文章名称的占位符(参数)。

hash-maps不同,这种树结构还允许我们使用像:post参数这种动态部分,因为我们实际上是根据路由模式进行匹配,而不仅仅是比较哈希值。

由于URL路径具有层次结构,并且只使用有限的一组字符(字节值),所以很可能有许多常见的前缀。这使我们可以很容易地将路由简化为更小的问题

此外,路由器为每种请求方法管理一棵单独的树

一方面,它比在每个节点中都保存一个 method-> handle map 更加节省空间,它还使我们甚至可以在开始在前缀树中查找之前大大减少路由问题。

为了获得更好的可伸缩性,每个树级别上的子节点都按Priority(优先级)排序,其中优先级(最左列)就是在子节点(子节点、子子节点等等)中注册的句柄的数量。【树上的节点越多的话,优先级越高】

为什么要这么做呢?

首先当去匹配一个路由的时候!你在一颗最长的树上找到的概率更大一点!反正你在一颗小树找到的概率就小一点!所以我们优先去做概率大的事情,去找小树的行为也相当于一种赌博~如果直接能在小树上找到那还好,如果没有找到,那么还要去大树中去找!在概率学中,当实验次数达到一定数量级的时候,优先去做大概率成功的事情是最优的选择!

所以一般的路由匹配优先级可以是下面这样~ 每个-可以看做一个节点匹配的路径:从左到右,从上到下。

   ├------------
   ├---------
   ├-----
   ├----
   ├--
   ├--
   └-

总结一下

radix树是一种根据公共前缀作为节点的树!这种树的优势在于相对于用map存储来说!运行占用的内存不会那么大!

然后给树节点增加优先级的方式,优化路径查找的效率!

0

评论区