路由查找之Radix Tree

路由查找之 Radix Tree

摘要

什么是Radix Tree 在计算机科学中，基数树，或称Patricia trie/tree，或crit bit tree，压缩前缀树，是一种更节省空间的Trie（前缀树）。对于基数树的每个节点，如果该节点是唯一的子树的话，就和父节点合并。 golang的web框架echo和gin都使用了radix tree作为路由查找的算法，我们以gin的实现来分析一下。 在gin的路由中，每一个Http