普通 Trie 在海量词库下变慢主因是内存分配和 GC 压力，而非算法复杂度；DAT 通过 base/check 数组实现无指针、无哈希的 O(m) 前缀查找，但仅支持静态词库且需预排序。
为什么普通 Trie 在海量词库下变慢
不是算法复杂度问题，而是内存分配和 GC 压力。10 万+ 词插入普通 map[rune]*Node 后，节点指针散乱、缓存不友好，每次 range word + node.children[r] 都触发哈希查找和指针跳转；更关键的是 DFS 自动补全时频繁拼接 prefix + string(r)，导致大量小字符串分配，GC 频繁 STW。
双数组 Trie（DAT）真正快在哪
DAT 把整棵树压进两个 []int 数组：base 和 check，所有状态转移变成纯数组索引计算，无指针、无哈希、无内存碎片：
-
base[i]表示节点i的子节点起始偏移量 -
check[base[i] + code(c)] == i才表示字符c是节点i的合法子边 - 查找一个前缀只需
O(m)次数组访问（m是前缀长度），比 map 查找快 3–5 倍
但它只适合静态词库——构建后不能动态增删，且词必须预排序（如按字典序），否则 base 分配会失败。
Go 中用 darts-go 实现 DAT 的关键点
别自己从零写 DAT，直接用成熟的 darts-go（GitHub 上 star 最多的 Go DAT 实现）：
立即学习“go语言免费学习笔记（深入）”；
- 构建前必须对词表排序：
sort.Strings(words)，否则Build()会 panic 或结果错乱 - 加载时用
dat.LoadFromBytes(data)而非反复Build()，二进制序列化后加载快 10 倍 - 搜索返回的是词在原始切片中的索引，不是字符串本身，需自行查表：
words[idx] - 不支持 Unicode 变长字符的直接编码——
darts-go默认用byte编码，中文需先转[]byte(unsafe.String(...))或改用支持 rune 的 fork 版本
什么时候该忍着不用 DAT
DAT 不是银弹。如果你的场景满足以下任一条件，坚持用普通 Trie 更省心：
- 词库每小时更新，需要在线
Insert()/Delete() - 业务含 emoji 或生僻汉字（如「?」「?」），而你没改过
darts-go的字符编码逻辑 - QPS
- 团队里没人读得懂 DAT 的 base/check 冲突检测逻辑，出问题只能重导词表
DAT 的构建耗时不可忽视：100 万词排序 + 构建常需 3–8 秒，这期间服务若依赖它，就得预热或降级。真正的性能瓶颈，往往卡在你没想到的 I/O 或锁竞争上，而不是 trie 本身。
