一句话定义：Trie（前缀树，也叫字典树、Prefix Tree）是一种按字符逐位往下分叉的树形查找结构——每个节点代表一个"前缀"，从根节点走到某个节点的路径拼起来，就是词表里的一个词或词的一部分。
用生活场景讲原理
想象一栋专门给单词住的公寓楼。一楼只有一个入口，进门先选首字母：走 a 门、b 门还是 c 门；进了 a 门再选第二个字母，再选第三个……所有以 ap 开头的词（app、apple、apply、ape）都走同一条 a→p 的走廊，到第三个字母才分岔。
于是树里每个节点只需要存两样东西：一个"我是不是某个词的结尾"的标记，一张"下一个字母去哪个孩子"的映射表。查一个词 apple，就是顺着 a→p→p→l→e 走五步；查前缀 app，走三步就到了一棵子树，子树里所有带结尾标记的节点，就是全部以 app 开头的词。
关键性质：查询耗时只和查询串长度 L 有关，约 O(L)，跟词表里有多少个词基本无关。词表从一万条涨到一百万条，查一个词该走几步还是几步——只是树变宽变深，单次查询的路径长度不变。代价是内存：指针和子节点表要占地方，属于典型的"空间换时间"。
和相邻结构的区别
| 结构 | 查整词 | 查前缀 | 词表变大时 | 典型用途 |
|---|---|---|---|---|
| Trie 前缀树 | O(L) | O(L)，天然支持 | 单次查询基本不变 | 自动补全、敏感词过滤、前缀缓存 |
| 哈希表 | 平均 O(1) | 不支持 | 冲突增多、需扩容 | 精确匹配、去重 |
| 有序数组 + 二分 | O(L·logN) | 可以但要扫相邻区间 | 变慢 | 小规模词表 |
| 倒排索引 | — | 面向全文检索 | — | 搜索引擎 |
一句话记：哈希表擅长"这个整体在不在"，Trie 擅长"以这串开头的都有谁"。
对从业者的实际意义
1. 自动补全：搜索框、输入法、命令行补全，本质都是"走完用户已输入的前缀，把子树里的候选词按热度排序吐出来"。走前缀这一步是 O(L)，所以输入再快也不卡。
2. 敏感词过滤：把词库建成 Trie，一次扫描文本即可同时匹配所有词；再做 Aho–Corasick 自动机（给 Trie 每个节点加"失配指针"），就能做到扫描一遍命中全部关键词，评论审核、弹幕过滤常用这套。
3. 前缀缓存复用：大模型推理时，很多请求的开头 prompt 是相同的（同一段系统提示、同一份文档）。把已算过的上下文按前缀组织成树，相同前缀只算一次、后面直接复用，这是当前推理加速里很核心的一类优化。不少推理框架用前缀树或基数树（radix tree）来组织这类缓存，具体实现和参数各家不同，以对应项目的官方文档为准。
4. 其他常见用途：IP 路由表的最长前缀匹配、拼写检查与模糊纠错、词频统计。
写代码时有个常见坑：如果字符集很大或很稀疏，别用定长数组存子节点，改用哈希表或"左孩子右兄弟"结构，否则内存会爆。另外，节点上除了"是否成词"的标记，通常还会挂一个计数值或权重，用来给补全候选排序。