The router relies on a tree structure which makes heavy use of common prefixes, it is basically a compact prefix tree (or just Radix tree). Nodes with a common prefix also share a common parent.

如果沿着从树根到叶的路径穿过树,则会得到完整的路径

Since URL paths have a hierarchical structure and make use only of a limited set of characters (byte values), it is very likely that there are a lot of common prefixes. This allows us to easily reduce the routing into ever smaller problems. Moreover the router manages a separate tree for every request method. For one thing it is more space efficient than holding a method->handle map in every single node, it also allows us to greatly reduce the routing problem before even starting the look-up in the prefix-tree.

由于URL路径具有层次结构,并且仅使用有限的字符集(字节值),因此很可能存在许多公共前缀。这使我们可以轻松地将路由减少到越来越小的问题中。此外,路由器为每种请求方法管理一棵单独的树。一方面,它比在每个单个节点中保存method-> handle map更加节省空间,它还使我们甚至可以在开始在前缀树中查找之前极大地减少路由问题。


参考:

go路由httprouter中的压缩字典树算法图解及c++实现

Trie三兄弟——标准Trie、压缩Trie、后缀Trie

如何克服字典树(Trie Tree)的缺点?

Trie树(压缩Trie树及Double-Array Trie)

看动画轻松理解「Trie树」

Trie(前缀树/字典树)及其应用

httprouter

Linux 内核中的数据结构:基数树(radix tree)

维普期刊

Radix树

数据结构之Radix Tree

基数树

这使得基数树更适用于对于较小的集合(尤其是字符串很长的情况下)和有很长相同前缀的字符串集合。

基数树的查找方式也与常规树不同(常规的树查找一开始就对整个键进行比较,直到不相同为止),基数树查找时节点时,对于节点上的键都按块进行逐块比较,其中该节点中块的长度是基数r; 当r为2时,基数树为二进制的(即该节点的键的长度为1比特位),能最大程度地减小树的深度来最小化稀疏性(最大限度地合并键中没有分叉的节点)。 当r≥4且为2的整数次幂时,基数树是r元基数树,能以潜在的稀疏性为代价降低基数树的深度。



Trie

leetcode上的字典树问题