介绍

首先介绍一下什么是路由，**路由就是根据请求信息将请求定位到具体的实现逻辑的过程**

这个过程我们称之为 **路由寻址**

而衡量路由的性能就是通过寻址的时间来判断，时间越短性能越高

传统路由结构

我们都用过 `expess` 或者 `koa + koa-router` 来开发项目

它们通过数组的形式保存路由映射表，通过**正则匹配**的方式遍历路由表来进行寻址

这种方式直观、简单，但是路由多的情况下，会消耗非常多的资源去做大量不必要的匹配

基于"前缀树"的路由结构

为了提升寻址能力，我们可以使用空间换时间的方式，将请求 path 拆分后，以特殊的数据结构存储

存储

我们注册如图4个路由：

首先，所有路由按照请求 method 分成对应的 method 树

然后将请求根据 `/` 拆封后，组装成树形结构

**为了提升匹配性能，存储节点的时候会保存节点类型，然后根据类型进行匹配**

搜索

我们拿到请求路径之后，同样根据`/`拆分，

首先根据 method 找到对应的树

然后在树中进行递归搜索，如果匹配到当前节点，则进行下一层搜索

每个节点都分为两种类型： 正则、字符串

如果当前节点为正则类型则使用正则匹配，适用于正则路由与参数路由等

如果当前节点为字符串类型则使用权等匹配，减少正则匹配次数，提升性能

优化

为了更大的性能提升（减少匹配次数），将节点进行优先级分类，将经过节点的路径最多的节点排在前面

这样将热门路由放在前面，用最少的次数就可以匹配到（后续可以增加手动设置优先级功能）

基准测试

机器比较烂，对比一下就好....

Dazejs + 1000个路由

| Stat      | Avg      | Stdev  | Min      |

| --------- | -------- | ------- | -------- |

| Req/Sec  | 33122.91 | 2705.63 | 25830    |

| Bytes/Sec | 4.8 MB  | 2.64 KB | 25.22 KB |

Express + 1000个路由

| Stat      | Avg      | Stdev  | Min    |

| --------- | -------- | ------- | ------- |

| Req/Sec  | 11809.64 | 1232.99 | 8115    |

| Bytes/Sec | 2.42 MB  | 1.2 KB  | 7.92 KB |

 Koa + Koa-router + 1000个路由

| Stat      | Avg        | Stdev  | Min    |

| --------- | ---------- | ------ | ------- |

| Req/Sec  | 6851.46    | 571.17 | 5103    |

| Bytes/Sec | 1016.86 KB | 571 B  | 4.98 KB |

更多

项目地址

题外话

目前很多 node 应用都是中间层，一丢丢的路由寻址优化其实可以忽略