URL Router 背后的数据结构与算法
URL Router 将不同的URL映射到不同的处理函数，不管在前端后端都是一个重要的组件。本文将简要介绍用来实现 Router 的几种数据结构。
工作模式
Router 的工作模式通常分为两个阶段。
第一阶段：注册
输入一组确定的路径模式和处理函数，Router 解析路径模式，保存映射关系。
第二阶段：查找
输入一个路径，Router 查找对应的处理函数，输出结果。
举个例子：
1 <= "/posts/:post_id/comments/:id"
2 <= "/posts/:post_id/comments"
3 <= "/posts/:post_id"
4 <= "/posts"
5 <= "/comments"
6 <= "/comments/:id"
7 <= "/file/*file_path"
查找 "/posts/100/comments/200"，应该返回 1, 并且附带参数捕获 [("post_id", "100"), ("id", "200")].
查找 "/file/usr/bin/sudo"， 应该返回 7，附带 [("file_path", "/usr/bin/sudo")].
查找 "/asdqwe"， 应该返回 None.
常见功能
静态路径匹配：基本功能。
命名参数捕获：路径中可以包含动态部分，模式将动态部分命名，查找时要返回对应的捕获，也属于基本功能。
通配符：捕获某段以及某段之后的所有部分，这一功能对静态文件服务很重要。
嵌套路由：将包含某个前缀的所有路径转发到子路由器，例如 "/api/v1" 对应 v1 路由，"/api/v2" 对应 v2 路由，有利于模块化。
正则表达式：用正则作为路径模式，大幅提高自由度。
末尾斜杠修正：自动修正 "/home" 和 "/home/" 这类路径。
数据结构与算法
第一种：遍历
保存一个路径模式的数组，查询时挨个测试，返回第一个匹配。
毋庸置疑，这是速度最慢的，但也是扩展性最高的，能够轻易实现复杂的匹配。很多框架的 Router 实现为遍历测试正则表达式。
第二种：正则表达式集合
RegexSet 能够同时测试多个正则表达式，并返回哪些表达式匹配了字符串。
这种方法本质上是将多个正则表达式转换为更复杂的状态机，兼顾了效率和自由度。
第三种： 非确定有限状态自动机 (NFA)
URL 路径是分段的，如果有效利用模式中的信息，可以自动产生一个状态机来匹配，这也是正则表达式的实现原理。
状态机的实现方式和正则表达式集合有异曲同工之妙。理论效率相差不大，砍掉复杂的模式特性后能更加高效。
第四种：基数树
以下内容翻译整理自 julienschmidt/httprouter
URL 路径通常具有良好的层次结构，即大量的公共前缀，符合基数树的使用场合。
这是一棵基数树的示意图。
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>
树在多个路径的不同字符处分叉，从树根一直匹配到叶子结点，即可得到匹配结果。结点可以是静态字符串，也可以是动态占位符。
子结点的匹配顺序是有讲究的，将子结点按权值排序，其中权值是路径长度，更具体的模式具有更高的优先级。
基数树的查找时间取决于树的深度和选择子结点的时间。通常来说，结点深度越深，子结点数越小，选择越快。因此这种实现会非常高效。
这种方式的弊端在于无法有效支持正则表达式，要想支持，只能将其他方式拼凑过来。
第五种：多叉树
\
|- posts => 4
|- :post_id => 3
|- comments => 2
|- :id => 1
|- comments => 5
|- :id => 6
|- file => None
|- *file_path => 7
将 URL 路径模式分为多段，插入多叉树，树在相同段的不同静态串处分叉，动态占位符也可分出一叉。
以下代码摘自 http-rs/path-table
多叉树非常符合直觉，反应快的人已经在脑海中实现整个算法了。
多叉树的查找速度取决于树的深度和选择分叉的速度。基于分段的树的深度通常非常小，大约在十几以下，开发者不会没事写几十上百段的 URL 路径模式。哈希的查找速度也非常快。因此这种方式甚至是最高效的。
同样，速度的代价是灵活性，多叉树无法支持正则表达式，也不能支持非整段的捕获，
第六种：位集 (BitSet)
同样基于分段，对于一个输入的路径，只有每段都匹配某个模式，才能最终获得处理函数。这个匹配过程可以转换为布尔表达式求值，用位集来同时求每个模式的值。
1 <= "/posts/:post_id/comments/:id"
2 <= "/posts/:post_id/comments"
3 <= "/posts/:post_id"
4 <= "/posts"
5 <= "/comments"
6 <= "/comments/:id"
7 <= "/file/*file_path"
查找 "/posts/100/comments/200"
首先有一个位集 11111111，表示所有模式都启用。
第一段存储三个位集，表示有哪些模式在第一段的这个字符串有静态注册。
00001111 <= "posts"
00110000 <= "comments"
01000000 <= "file"
选择 00001111，和 11111111 做与运算，得 00001111
第二段存储有一个位集，表示有哪些模式在第二段有动态注册。
01100111 <= dynamic
选择 01100111，和 00001111 做与运算，得 00000111
第三段
00000011 <= "comments"
求与得 00000011
第四段
00000001 <= dynamic
求与得 00000001
所有段匹配完毕，位集中有一个 1，位置是最右边，即第 1 位，表示第 1 个模式完全匹配，匹配成功。
为了支持其他功能，还要仔细添加算法细节，才能做到正确。
位集方式的查找速度取决于段数和每段中查找特定字符串的速度，还与位集的运算速度有关。如果仅支持不多于128个的模式，就可以用 u128 实现位集，用一条 SSE 指令实现运算。最终速度能比多叉树还快。
为了更快的速度，位集方式加上了数量限制。
总结
选择 URL Router 算法，无非是用自由换性能，用性能换自由，符合需要的就是好的。
Rust crates
遍历+正则 actix-router
正则表达式集合 reset-router
NFA route-recognizer
基数树 path-tree
多叉树 path-table