搜索框要做输入联想，词库十万条，每敲一个字母都从头遍历，输入两个字符页面就卡住。改成字典树之后，同样的机器，响应时间从一百多毫秒降到几毫秒。
它到底存了什么
字典树也叫 Trie，把每个字符串按字符拆开，从根节点往下串。根节点是空的，每个节点存一个字符，从根到某个节点的路径就是一个前缀。公共前缀只存一份，比如「中国」「中间」「中文」共用「中」这个节点，后面再分叉。节点上一般加一个标记，表示这里是不是一个完整单词的结尾。查的时候从根开始，一个字符一个字符往下走，走不动就说明没有；走到底再看标记，判断是前缀还是完整词。
插入和查询的代价
插入一个长度为 L 的词，时间复杂度是 O(L)，和词库多大没关系。查询同样只跟待查串长度有关，这就是它比线性遍历快的原因。前缀搜索、敏感词过滤、输入法联想、IP 路由表，底层都常见它的影子。
class TrieNode { constructor() { this.children = new Map(); this.isEnd = false; } }中文场景要注意内存
英文只有 26 个字母，子节点可以用定长数组，查起来快。中文常用字几千个，再用数组就浪费，一般用 Map 或者对象按需挂子节点。词库特别大时，内存占用会比原词库高好几倍，这是典型的用空间换时间。
实际项目里还会给节点加两个字段：一个记录经过该节点的词条数量，用来给联想结果排序；一个记录子节点个数，方便剪枝。要支持删除，把结尾标记改回 false 就行，节点本身留着，避免频繁增删产生内存碎片。面试让手写 Trie 时，插入和查找写清楚，isEnd 别漏，基本就够看了。
词库上百万条时，普通对象节点会吃掉大量内存，可以考虑双数组 Trie，或者按首字拆成多棵小树，用到哪棵加载哪棵。搜索联想通常再加一层缓存，热门前缀的结果直接存下来，不必每次都走一遍树。
字典树不是万能钥匙。只做完整匹配，哈希表更省事；前缀查询多、词库相对固定，它才划算。上线前拿真实词库压一遍内存，别等服务器报警才发现节点比词条还多。