Node.js路由包Anumargak异常性能问题排查求助

嘿，我明白你在Anumargak上遇到的性能瓶颈问题了——全量遍历二维数组来查找路由确实会随着注册路由的增多变得越来越慢，尤其是每次调用on时还要先跑一遍find，这相当于双重的线性遍历开销，当路由数量达到几百上千条时，性能下降会非常明显。

问题核心分析 #

当前实现的问题在于：

• 路由存储用的是二维数组，每次find和on前的重复检查都需要**O(n)**的时间复杂度（n是路由总数）
• 随着路由数量增长，这种线性遍历的耗时会呈指数级上升，最终导致性能异常

优化方案：改用路由树（Trie）存储结构 #

HTTP路由天然具备层级结构（比如/some/url可以拆分为some、url两个路径段），用路由树（也叫前缀树）来存储路由，能把查找和插入的时间复杂度降到O(k)（k是路由的路径段数量），性能提升非常显著。

具体实现思路

1. 按HTTP方法分层：先创建一个顶层对象，用HTTP方法（如GET、POST）作为key，每个key对应一棵独立的路由树，这样不同方法的路由不会互相干扰。
2. 路由树节点结构：每个节点包含：
   • children：一个对象，存储静态路径段到子节点的映射
   • paramChild：存储动态路径段（如:userId）对应的子节点
   • wildcardChild：存储通配符（如*）对应的子节点
   • handler：当前路径对应的处理函数（如果该节点是一个完整路由的终点）
3. 重构on方法：
   • 将路由路径按/分割成路径段（注意过滤空字符串，比如根路径/分割后会有空值）
   • 从对应方法的路由树根节点开始，逐层遍历路径段，不存在的节点就创建新节点
   • 最后在终点节点挂载处理函数，无需额外调用find做重复检查（插入过程中就能自然判断是否重复）
4. 重构find方法：
   • 同样分割路径段，逐层遍历路由树
   • 遇到动态路径段时，记录参数值；遇到通配符时直接匹配剩余所有路径
   • 最终返回找到的处理函数和提取的参数

简化代码示例

function Anumargak() {
  // 按HTTP方法存储路由树
  const routes = {
    GET: createRouteNode(),
    POST: createRouteNode(),
    // 可扩展其他HTTP方法...
  };

  function createRouteNode() {
    return {
      children: {},
      paramChild: null,
      wildcardChild: null,
      handler: null,
      paramName: '' // 存储动态参数的名称，比如":userId"中的"userId"
    };
  }

  return {
    on(method, path, handler) {
      const segments = path.split('/').filter(s => s);
      const upperMethod = method.toUpperCase();
      let currentNode = routes[upperMethod] || (routes[upperMethod] = createRouteNode());
      
      for (const segment of segments) {
        if (segment.startsWith(':')) {
          // 处理动态参数路由
          if (!currentNode.paramChild) {
            currentNode.paramChild = createRouteNode();
            currentNode.paramChild.paramName = segment.slice(1);
          }
          currentNode = currentNode.paramChild;
        } else if (segment === '*') {
          // 处理通配符路由
          if (!currentNode.wildcardChild) {
            currentNode.wildcardChild = createRouteNode();
          }
          currentNode = currentNode.wildcardChild;
          break; // 通配符匹配剩余所有路径，无需继续遍历
        } else {
          // 处理静态路由
          if (!currentNode.children[segment]) {
            currentNode.children[segment] = createRouteNode();
          }
          currentNode = currentNode.children[segment];
        }
      }
      
      // 挂载处理函数，若已有则覆盖（可根据需求调整为报错）
      currentNode.handler = handler;
    },

    find(method, path) {
      const segments = path.split('/').filter(s => s);
      const upperMethod = method.toUpperCase();
      let currentNode = routes[upperMethod];
      const params = {};
      
      if (!currentNode) return null;

      for (let i = 0; i < segments.length; i++) {
        const segment = segments[i];
        if (currentNode.children[segment]) {
          currentNode = currentNode.children[segment];
        } else if (currentNode.paramChild) {
          // 提取动态参数值
          params[currentNode.paramChild.paramName] = segment;
          currentNode = currentNode.paramChild;
        } else if (currentNode.wildcardChild) {
          currentNode = currentNode.wildcardChild;
          break;
        } else {
          // 未找到匹配的路由
          return null;
        }
      }
      
      // 检查通配符节点的处理函数
      if (currentNode.wildcardChild) {
        currentNode = currentNode.wildcardChild;
      }
      
      return currentNode.handler ? { handler: currentNode.handler, params } : null;
    }
  };
}

额外优化建议 #

• 可以添加路由重复注册的检测逻辑，在on方法插入节点时，如果终点节点已有handler，可以抛出警告或错误
• 对于复杂的正则路由，可以在节点中扩展regexChild字段，但需要注意正则匹配的性能开销，建议优先使用静态/动态/通配符路由
• 可以缓存高频访问的路由结果，进一步提升查找速度

内容的提问来源于stack exchange，提问作者Amit Kumar Gupta