34｜前缀树：Web框架中如何实现路由匹配？
黄清昊
该思维导图由 AI 生成，仅供参考
你好，我是微扰君。
不知不觉，已经到工程实战篇的最后一讲了，在这个章节中，我们一起学习了很多工程中常用的算法，如果你从事后端开发，应该或多或少有些接触，比如在 Redis、Kafka、ZooKeeper 等常用中间件里就经常出现，理解它们的核心思想，能给你的工作带来很大的帮助。
今天，我们最后来聊一聊大部分 Web 开发工程师都会用到的后端 Web 框架中的算法。
路由匹配
Web 框架的作用，我们都知道，主要就是封装 Web 服务，整合网络相关的通用逻辑，一般来说也就是帮助 HTTP 服务建立网络连接、解析 HTTP 头、错误恢复等等；另外，大部分框架可能也会提供一些拦截器或者 middleware，帮助我们处理一些每个请求可能都需要进行的操作，比如鉴权、获取用户信息。
但是所有 Web 框架，无论设计得多么不同，必不可少的能力就是路由匹配。
因为我们的 Web 服务通常会对外暴露许多不同的 API，而区分这些 API 的标识，主要就是用户请求 API 的 URL。所以，一个好用的 Web 框架，要能尽可能快地解析请求 URL 并映射到不同 API 的处理逻辑，也就是我们常说的“路由匹配”。
以 Golang 中常用的 Web 框架 Gin 为例，如果用户想注册一套遵循 RESTful 风格的接口，只需要像这样，写一下注册每个路由所对应的 handler 方法就完成了：
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了Trie树在Web框架中实现路由匹配的技术原理及应用。Trie树是一种高效的有序集合实现，特别适合于前缀匹配的场景，如字符串检索、敏感词过滤、搜索推荐等。文章重点讨论了Trie树的数据结构和实现方式，以及其在动态路由匹配中的应用。通过示意图和代码演示，读者可以了解Trie树的存储方式和特点，以及如何在Web框架中实现路由匹配。此外，文章还提到了Trie树的空间效率问题，并留下了课后思考题，引发读者思考如何优化Trie树的实现。总的来说，本文内容深入浅出，适合对Web框架路由匹配感兴趣的读者阅读学习。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《业务开发算法 50 讲》，新⼈⾸单¥59
《业务开发算法 50 讲》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(4)
- 最新
- 精选
csyangchshradix trie作者回复: 嗯嗯 之后的加餐会讲解 radix tree
2022-03-131- Paul Shan前缀树的空间浪费可以用hashmap来优化，key对应的字母，value对应下一层的指针。这种方案在节点数量多的时候反而要浪费更大的空间，因为hashmap需要一定的空余空间，而且key之间的顺序信息也丢失了。
作者回复: 嗯嗯 有序也是前缀树的一个很大的优势
2022-03-12 
peter请教老师一个问题： Q1：如果是中文，字符集怎么处理？ 文中例子是英文，字符集确定而且很小。但如果是中文，字符集太大了，怎么处理？2022-03-1311
nbsp;前缀树里字母是路径不是节点2022-05-16
收起评论
