PHP自定义URL路由：Trie树/Radix Tree的高性能应用
大家好，今天我们来深入探讨一个在Web开发中至关重要的话题：PHP中的自定义URL路由，以及如何利用Trie树（也称为前缀树）和Radix Tree（基数树）来构建高性能的路由匹配系统。
1. 路由的重要性与常见方案的局限性
在现代Web应用中，路由扮演着至关重要的角色。它负责将用户发出的URL请求映射到相应的处理程序（Controller、函数等），从而决定服务器如何响应这个请求。一个好的路由系统应该具备以下特点：
- 准确性: 正确地匹配URL到对应的处理程序。
- 性能: 高效地处理大量的URL请求，保证应用的响应速度。
- 灵活性: 支持各种复杂的路由规则，例如参数、可选参数、通配符等。
- 可维护性: 易于配置、修改和扩展。
常见的PHP路由方案包括：
- 基于if/else或switch语句的简单匹配: 适用于路由规则较少的情况，但随着规则增加，代码会变得臃肿不堪，难以维护，且性能会线性下降。
- 基于正则表达式的匹配: 灵活性较高，可以处理复杂的路由规则。但是正则表达式的匹配效率相对较低，尤其是在需要匹配大量路由规则时，性能瓶颈会非常明显。同时，复杂的正则表达式也增加了代码的维护难度。
- 基于数组查找的匹配: 将路由规则存储在数组中，然后使用
in_array或array_key_exists等函数进行查找。这种方法在路由规则较少时性能尚可，但随着规则增多，查找效率会线性下降。许多框架使用数组保存路由信息，配合哈希查找，本质上也是空间换时间。
这些方案在处理大规模URL路由时都存在一定的局限性，无法同时满足高性能和灵活性的需求。因此，我们需要寻找更高效的数据结构和算法来实现URL路由。
2. Trie树 (前缀树) 的原理与应用
Trie树，又称前缀树或字典树，是一种用于存储字符串的树形数据结构。它的每个节点代表一个字符串的前缀，根节点代表空字符串。从根节点到任意节点的路径上的字符连接起来，就构成了该节点所代表的字符串。Trie树的关键特性是，所有具有相同前缀的字符串共享相同的前缀节点。
例如，我们要存储以下字符串： "app", "apple", "beer", "bee", "bear"。 对应的Trie树结构如下：
(root)
/
a b
/
p e
/ /
p p e a
| | | |
l l r r
| e |
e r在URL路由中，我们可以将每个URL路径视为一个字符串，然后将其存储在Trie树中。当收到一个URL请求时，我们可以从根节点开始，沿着URL路径逐个字符地向下遍历Trie树，直到找到匹配的叶子节点。叶子节点通常会存储与该URL路径关联的处理程序信息。
PHP代码实现一个简单的Trie树：
<?php
class TrieNode {
public $children = [];
public $handler = null; // 存储与该URL关联的处理程序
public $isEndOfPath = false; // 标记是否为完整路径的结尾
}
class TrieRouter {
private $root;
public function __construct() {
$this->root = new TrieNode();
}
/**
* 添加路由规则
*
* @param string $path URL路径
* @param callable $handler 处理程序
*/
public function addRoute(string $path, callable $handler): void {
$node = $this->root;
$parts = explode('/', trim($path, '/')); // 分割URL路径
foreach ($parts as $part) {
if (!isset($node->children[$part])) {
$node->children[$part] = new TrieNode();
}
$node = $node->children[$part];
}
$node->handler = $handler;
$node->isEndOfPath = true;
}
/**
* 查找路由
*
* @param string $path URL路径
* @return callable|null 返回处理程序，如果未找到则返回null
*/
public function matchRoute(string $path): ?callable {
$node = $this->root;
$parts = explode('/', trim($path, '/'));
foreach ($parts as $part) {
if (!isset($node->children[$part])) {
return null; // 未找到匹配的路由
}
$node = $node->children[$part];
}
if ($node->isEndOfPath && $node->handler !== null) {
return $node->handler; // 找到匹配的路由
} else {
return null; // 路径存在，但不是一个完整的路由
}
}
}
// 示例用法
$router = new TrieRouter();
$router->addRoute('/users', function() {
return 'List of users';
});
$router->addRoute('/users/create', function() {
return 'Create a new user';
});
$router->addRoute('/products/123', function() {
return 'Product detail for ID 123';
});
echo $router->matchRoute('/users')() . "n"; // 输出: List of users
echo $router->matchRoute('/users/create')() . "n"; // 输出: Create a new user
echo $router->matchRoute('/products/123')() . "n"; // 输出: Product detail for ID 123
echo $router->matchRoute('/products/456') . "n"; // 输出:在这个例子中，我们创建了一个简单的 TrieRouter 类，它使用 TrieNode 类来构建Trie树。 addRoute 方法用于添加路由规则，matchRoute 方法用于查找匹配的路由。
Trie树的优点：
- 前缀匹配: Trie树擅长前缀匹配，这非常适合URL路由，因为URL路径通常具有相同的前缀。
- 查找效率高: 查找时间复杂度为 O(k)，其中 k 是URL路径的长度，与路由规则的数量无关。这意味着即使有大量的路由规则，查找速度仍然很快。
- 空间效率: 共享前缀可以节省存储空间。
Trie树的局限性：
- 对于长路径，空间占用较大: 如果URL路径很长且没有很多共享前缀，Trie树可能会占用较多的内存。
- 不支持通配符和参数: 基本的Trie树无法直接支持通配符和参数匹配，需要进行扩展。
3. Radix Tree (基数树) 的原理与应用
Radix Tree，也称为压缩前缀树或PATRICIA tree，是对Trie树的一种优化。它通过将连续的单字符节点合并为一个节点来减少树的高度，从而提高查找效率和节省存储空间。
例如，在上面的Trie树例子中，路径 "/apple" 包含了连续的单字符节点 "a" -> "p" -> "p" -> "l" -> "e"。 在Radix Tree中，这些节点可以合并为一个节点 "apple"。
PHP代码实现一个简单的Radix Tree：
<?php
class RadixNode {
public $prefix = ''; // 存储路径片段
public $children = [];
public $handler = null;
public $isEndOfPath = false;
}
class RadixRouter {
private $root;
public function __construct() {
$this->root = new RadixNode();
}
/**
* 添加路由规则
*
* @param string $path URL路径
* @param callable $handler 处理程序
*/
public function addRoute(string $path, callable $handler): void {
$path = trim($path, '/');
$this->insert($this->root, $path, $handler);
}
private function insert(RadixNode $node, string $path, callable $handler): void {
if ($path === '') {
$node->handler = $handler;
$node->isEndOfPath = true;
return;
}
foreach ($node->children as $child) {
if (strpos($path, $child->prefix) === 0) { // 找到匹配的前缀
$prefixLength = strlen($child->prefix);
$remainingPath = substr($path, $prefixLength);
if ($remainingPath === '') { //完全匹配
$child->handler = $handler;
$child->isEndOfPath = true;
} else {
$this->insert($child, $remainingPath, $handler); // 递归插入剩余路径
}
return;
} elseif (strspn($path, $child->prefix) > 0) { // 部分匹配，需要分割节点
$commonPrefixLength = strspn($path, $child->prefix);
$commonPrefix = substr($child->prefix, 0, $commonPrefixLength);
$childOriginalPrefix = $child->prefix;
$child->prefix = $commonPrefix;
$newChild = new RadixNode();
$newChild->prefix = substr($childOriginalPrefix, $commonPrefixLength);
$newChild->children = $child->children;
$newChild->handler = $child->handler;
$newChild->isEndOfPath = $child->isEndOfPath;
$child->children = [$newChild];
$child->handler = null;
$child->isEndOfPath = false;
$remainingPath = substr($path, $commonPrefixLength);
$newNode = new RadixNode();
$newNode->prefix = $remainingPath;
$newNode->handler = $handler;
$newNode->isEndOfPath = true;
$child->children[] = $newNode;
return;
}
}
// 没有找到匹配的前缀，创建新的节点
$newNode = new RadixNode();
$newNode->prefix = $path;
$newNode->handler = $handler;
$newNode->isEndOfPath = true;
$node->children[] = $newNode;
}
/**
* 查找路由
*
* @param string $path URL路径
* @return callable|null 返回处理程序，如果未找到则返回null
*/
public function matchRoute(string $path): ?callable {
$path = trim($path, '/');
return $this->search($this->root, $path);
}
private function search(RadixNode $node, string $path): ?callable {
if ($path === '') {
if($node->isEndOfPath && $node->handler !== null){
return $node->handler;
} else {
return null;
}
}
foreach ($node->children as $child) {
if (strpos($path, $child->prefix) === 0) {
$prefixLength = strlen($child->prefix);
$remainingPath = substr($path, $prefixLength);
return $this->search($child, $remainingPath);
}
}
return null;
}
}
// 示例用法
$router = new RadixRouter();
$router->addRoute('/users', function() {
return 'List of users';
});
$router->addRoute('/users/profile', function() {
return 'User profile';
});
$router->addRoute('/products/electronics', function() {
return 'Electronics products';
});
echo $router->matchRoute('/users')() . "n"; // 输出: List of users
echo $router->matchRoute('/users/profile')() . "n"; // 输出: User profile
echo $router->matchRoute('/products/electronics')() . "n"; // 输出: Electronics products
echo $router->matchRoute('/products/clothing') . "n"; // 输出:
在这个例子中，insert 函数负责将路由规则插入到Radix Tree中，search函数负责查找匹配的路由。 注意 insert 函数中对节点分割的逻辑，这是实现Radix Tree的关键。
Radix Tree的优点：
- 空间效率更高: 通过合并连续的单字符节点，Radix Tree可以显著减少树的高度和节点数量，从而节省存储空间。
- 查找效率更高: 由于树的高度降低，查找速度更快。
Radix Tree的局限性：
- 实现复杂: 相比于Trie树，Radix Tree的实现更加复杂，需要处理节点分割和合并等操作。
- 同样不支持通配符和参数: 仍然需要进行扩展才能支持通配符和参数匹配。
4. 高级路由：支持通配符和参数
为了支持更复杂的路由规则，例如 /users/{id} 或 /articles/*，我们需要对Trie树或Radix Tree进行扩展。 我们可以引入以下机制：
- 参数节点: 使用特殊的符号（例如
{}）来标记参数节点。在匹配时，参数节点可以匹配任意的字符串，并将匹配到的值提取出来。 - 通配符节点: 使用通配符（例如
*）来标记通配符节点。通配符节点可以匹配任意数量的字符。
以下是一个扩展Radix Tree以支持参数的示例：
<?php
class RadixNode {
public $prefix = '';
public $children = [];
public $handler = null;
public $isEndOfPath = false;
public $paramName = null; // 存储参数名称
}
class RadixRouter {
private $root;
public function __construct() {
$this->root = new RadixNode();
}
/**
* 添加路由规则
*
* @param string $path URL路径
* @param callable $handler 处理程序
*/
public function addRoute(string $path, callable $handler): void {
$path = trim($path, '/');
$this->insert($this->root, $path, $handler);
}
private function insert(RadixNode $node, string $path, callable $handler): void {
if ($path === '') {
$node->handler = $handler;
$node->isEndOfPath = true;
return;
}
// 参数处理
if (preg_match('/^{([a-zA-Z0-9_]+)}/', $path, $matches)) {
$paramName = $matches[1];
$node->paramName = $paramName;
$newNode = new RadixNode();
$newNode->prefix = '';
$newNode->handler = $handler;
$newNode->isEndOfPath = true;
$node->children[] = $newNode;
return;
}
foreach ($node->children as $child) {
if (strpos($path, $child->prefix) === 0) { // 找到匹配的前缀
$prefixLength = strlen($child->prefix);
$remainingPath = substr($path, $prefixLength);
if ($remainingPath === '') { //完全匹配
$child->handler = $handler;
$child->isEndOfPath = true;
} else {
$this->insert($child, $remainingPath, $handler); // 递归插入剩余路径
}
return;
} elseif (strspn($path, $child->prefix) > 0) { // 部分匹配，需要分割节点
$commonPrefixLength = strspn($path, $child->prefix);
$commonPrefix = substr($child->prefix, 0, $commonPrefixLength);
$childOriginalPrefix = $child->prefix;
$child->prefix = $commonPrefix;
$newChild = new RadixNode();
$newChild->prefix = substr($childOriginalPrefix, $commonPrefixLength);
$newChild->children = $child->children;
$newChild->handler = $child->handler;
$newChild->isEndOfPath = $child->isEndOfPath;
$child->children = [$newChild];
$child->handler = null;
$child->isEndOfPath = false;
$remainingPath = substr($path, $commonPrefixLength);
$newNode = new RadixNode();
$newNode->prefix = $remainingPath;
$newNode->handler = $handler;
$newNode->isEndOfPath = true;
$child->children[] = $newNode;
return;
}
}
// 没有找到匹配的前缀，创建新的节点
$newNode = new RadixNode();
$newNode->prefix = $path;
$newNode->handler = $handler;
$newNode->isEndOfPath = true;
$node->children[] = $newNode;
}
/**
* 查找路由
*
* @param string $path URL路径
* @return array|null 返回包含处理程序和参数的数组，如果未找到则返回null
*/
public function matchRoute(string $path): ?array {
$path = trim($path, '/');
return $this->search($this->root, $path);
}
private function search(RadixNode $node, string $path, array $params = []): ?array {
if ($path === '') {
if($node->isEndOfPath && $node->handler !== null){
return ['handler' => $node->handler, 'params' => $params];
} else {
return null;
}
}
//参数路由匹配
if ($node->paramName !== null) {
return ['handler' => $node->handler, 'params' => array_merge($params, [$node->paramName => $path])];
}
foreach ($node->children as $child) {
if (strpos($path, $child->prefix) === 0) {
$prefixLength = strlen($child->prefix);
$remainingPath = substr($path, $prefixLength);
return $this->search($child, $remainingPath, $params);
}
}
return null;
}
}
// 示例用法
$router = new RadixRouter();
$router->addRoute('/users/{id}', function($id) {
return "User ID: " . $id;
});
$router->addRoute('/articles/{category}/{articleId}', function($category, $articleId) {
return "Category: " . $category . ", Article ID: " . $articleId;
});
$match1 = $router->matchRoute('/users/123');
echo $match1['handler']($match1['params']['id']) . "n"; // 输出: User ID: 123
$match2 = $router->matchRoute('/articles/sports/456');
echo $match2['handler']($match2['params']['category'], $match2['params']['articleId']) . "n"; // 输出: Category: sports, Article ID: 456
echo $router->matchRoute('/products/electronics'); // 输出:在这个例子中，我们修改了 RadixNode 类，增加了一个 paramName 属性来存储参数名称。 在 insert 函数中，我们使用正则表达式来检测参数节点，并将参数名称存储在 paramName 属性中。 在 search 函数中，我们使用 preg_match 函数来匹配参数节点，并将匹配到的值存储在 $params 数组中。
5. 性能考量与优化
虽然Trie树和Radix Tree在理论上具有很高的查找效率，但在实际应用中，仍然需要考虑一些性能因素：
- 内存占用: 尤其是在路由规则非常多的情况下，Trie树和Radix Tree可能会占用大量的内存。 可以考虑使用更紧凑的数据结构或采用懒加载的策略来减少内存占用。
- 字符串操作: 频繁的字符串操作（例如
substr、strpos等）可能会影响性能。 可以尝试使用更高效的字符串操作函数或避免不必要的字符串操作。 - 缓存: 可以将常用的路由规则缓存起来，以减少查找次数。
不同方案的比较：
| 方案 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| if/else/switch | 简单易懂 | 随着路由规则增加，代码臃肿，性能下降 | 路由规则非常少的情况 |
| 正则表达式 | 灵活性高，可以处理复杂的路由规则 | 性能较低，维护难度大 | 路由规则复杂，但数量不多的情况 |
| 数组查找 | 实现简单 | 随着路由规则增加，查找效率下降 | 路由规则数量较少的情况 |
| Trie树 | 查找效率高，擅长前缀匹配 | 对于长路径，空间占用较大，不支持通配符和参数，实现复杂 | 路由规则数量较多，且具有较多共享前缀的情况，需要自行扩展参数和通配符 |
| Radix树 | 查找效率高，空间效率更高 | 实现复杂，不支持通配符和参数，实现复杂 | 路由规则数量较多，且具有较多共享前缀的情况，需要自行扩展参数和通配符 |
6. 选择合适的方案
选择哪种路由方案取决于具体的应用场景和需求。
- 如果路由规则非常少，且不需要支持复杂的路由规则，那么简单的
if/else或switch语句可能就足够了。 - 如果路由规则数量不多，但需要支持复杂的路由规则，那么基于正则表达式的匹配可能是一个不错的选择。
- 如果路由规则数量很多，且需要高性能的路由匹配，那么Trie树或Radix Tree是更好的选择。
在使用Trie树或Radix Tree时，需要根据实际情况进行优化，例如使用更紧凑的数据结构、缓存常用的路由规则等。
7. 更进一步：将想法付诸实践
今天我们讨论了PHP中自定义URL路由的实现方案，并重点介绍了Trie树和Radix Tree这两种高性能的数据结构。 希望通过今天的分享，大家能够对PHP路由有更深入的理解，并能够在实际项目中选择合适的方案，构建高性能的Web应用。
最后的建议：
- 根据实际需求选择合适的路由方案。
- 注重性能优化，减少内存占用和字符串操作。
- 编写清晰、可维护的代码。