**复杂度**
* 前缀树 O(n)
* map O(1)
从复杂度上看 前缀树 是大于 map 的
那么gin使用前缀树只是为了降低内存占用吗?
像下面这种场景,map也不太好实现
为了更具扩展性,每一层的节点按照priority排序,priority是节点的子节点(儿子节点,孙子节点等)注册的handler的数量,这样做有两个好处:
- 被最多路径包含的节点会被最先评估。这样可以让尽量多的路由快速被定位。
- 有点像成本补偿。最长的路径可以被最先评估,补偿体现在最长的路径需要花费更长的时间来定位,如果最长路径的节点能被优先评估(即每次拿子节点都命中),那么所花时间不一定比短路径的路由长。下面展示了节点(每个-可以看做一个节点)评估的路径:从左到右,从上到下
可以看下这篇文章,讲得挺好的 [路由查找之Radix Tree](https://michaelyou.github.io/2018/02/10/%E8%B7%AF%E7%94%B1%E6%9F%A5%E6%89%BE%E4%B9%8BRadix-Tree/)
#5