# 3.12 路由树-总结与面试要点

本节课工程结构如下:

```
(base) yanglei@yuanhong 17-summary % tree ./
./
├── context.go
├── handleFunc.go
├── httpServer.go
├── httpServer_test.go
├── matchNode.go
├── node.go
├── router.go
├── router_test.go
└── serverInterface.go

0 directories, 9 files
```

## PART1. 注册路由的注意事项

* 已经注册了的路由,无法被覆盖.例如`/user/home`注册两次,会冲突
* `path`必须以`/`开始并且结尾不能有`/`,中间也不允许有连续的`/`
* 不能在同一个位置注册不同的参数路由.例如`/user/:id`和`/user/:name`冲突
* 不能在同一个位置同时注册通配符路由和参数路由.例如`/user/:id`和`/user/*`冲突
* 同名路径参数,在路由匹配的时候,值会被覆盖.例如`/user/:id/abc/:id`,那么`/user/123/abc/456`,最终`id = 456`
  * TODO:这里是可以实现把2个id都记录下来的,只需要将`matchNode.pathParams`的类型修改为`map[string][]string`即可.下去自己试一下
  * TODO:这种情况也可以考虑panic掉

把以上内容作为注释放在`addRoute()`方法上,那么但凡用户发现panic的时候看一眼这个注释,都知道出了什么问题

`router.go`:

```go
// AddRoute 注册路由到路由森林中的路由树上
// 其中path为路由的路径.该路径:
// 1. 不得为空字符串
// 2. 必须以"/"开头
// 3. 不能以"/"结尾
// 4. 不能包含连续的"/"
// - 已经注册了的路由,无法被覆盖.例如`/user/home`注册两次,会冲突
// - `path`必须以`/`开始并且结尾不能有`/`,中间也不允许有连续的`/`
// - 不能在同一个位置注册不同的参数路由.例如`/user/:id`和`/user/:name`冲突
// - 不能在同一个位置同时注册通配符路由和参数路由.例如`/user/:id`和`/user/*`冲突
// - 同名路径参数,在路由匹配的时候,值会被覆盖.例如`/user/:id/abc/:id`,那么`/user/123/abc/456`,最终`id = 456`
func (r *router) addRoute(method string, path string, handleFunc HandleFunc)
```

## PART2. 为什么在注册路由用`panic`?

可以看到在`addRoute()`方法中有大量的panic出现.

那么问题来了:

* 可不可以返回`error`?
* 应不应该返回`error`?

### 2.1 可不可以返回`error`?

可以返回,但没必要.因为框架的使用者根本不会去处理的.注册路由都失败了,谁还有空去处理注册路由的报错信息呢?

### 2.2 应不应该返回`error`?

其实不应该.从框架使用者的角度上来看,用户**必须完成注册路由的步骤,才能启动HTTPServer**.那么在注册路由时,采用`panic`就是没问题的,因为这时应用还没运行.

注册路由时`panic`总好过应用启动了再`panic`.

## PART3. 路由树是线程安全的吗?

显然不是线程安全的.我们要求用户必须要注册完路由才能启动`HTTPServer`.而正常的用法都是在启动之前**依次**注册路由,不存在并发场景.

换言之,这是一个顺序写并发读的场景.并不会出问题.并发读写才会引入线程安全问题.

至于运行期间动态注册路由,没必要支持.这是典型的**为了解决1%的问题,引入99%的代码**.

之所以不将路由树做成线程安全的,也是为了性能,因为一旦涉及到加锁/原子操作的情况,性能就下来了.

## PART4. 面试要点(一)

### 4.1 路由树算法的实现?

**核心就是前缀树**.前缀的意思就是,两个节点共同的前缀,将会被抽取出来作为父节点.在我们的实现中是按照`/`来切割,每一段作为一个节点.

### 4.2 路由匹配的优先级?

本质上这是和Web框架相关的.在我们的设计里面是`静态匹配 > 路径参数 > 通配符匹配`.但实际上这个规则意义不大,因为路径参数和通配符匹配是互斥的

### 4.3 路由查找会回溯吗?

这也是和Web框架相关的,我们在课程上是不支持的.在这里可以简单描述可回溯和不可回溯之间的区别,可以是用课程中的例子`/user/123/home`和`/user/*/*`.课程中不支持是因为这个特性非常鸡肋

### 4.4 Web框架是怎么组织路由树的?

一个HTTP动词就是一颗路由树.也可以考虑所有HTTP动词共用一颗路由树,每个节点标记自己支持的HTTP方法.前者是比较主流的

TODO:第二种可以尝试去写

## PART5. 面试要点(二)

### 5.1 路由查找的性能受什么影响? 或者说怎么评估路由查找的性能?

**核心是看路由树的高度,次要因素是路由树的宽度(想想我们的`node.children`字段)**.

但是我们实现的时候`node.children`字段用的是`map`来实现的,所以宽度对我们的实现影响不大.但是如果使用`slice`实现,宽度影响就比较大了.

GIN的最长前缀树,则树会更高;我们的实现中,树会更宽.

如果你不是为了装逼,不要写GIN的那种路由树,因为代码很复杂,且很难读懂.

### 5.2 路由树是线程安全的吗?

严格来说也是跟Web框架相关的.大多数都不是线程安全的,这是为了性能.所以才要求大家一定要先注册路由,后启动Web服务器.如果你有运行期间动态添加路由的需求,只需要利用装饰器模式,就可以将一个线程不安全的封装为线程安全的路由树.

### 5.3 具体匹配方式的实现原理?

课程上我们实现了静态匹配、通配符匹配和路径匹配，作业里面要求大家照着实现一个正则匹配.**其实核心就是划定优先级,然后一种种匹配方式挨个匹配过去**.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://go.sai.show/part03.-lu-you-shu/3.12-lu-you-shu-zong-jie-yu-mian-shi-yao-dian.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.