已有一百万个关键词时，如何设计输入联想推荐，支持前缀匹配、热度排序、更新、内存控制和低延迟返回？｜滴滴后端开发面经解析

60 秒回答模板

我会把系统拆成召回、排序、更新、存储和服务五层。一百万关键词规模不算特别大，核心要求是输入前缀后毫秒级返回 TopK 建议。召回层可以用 Trie 或压缩 Trie：每条从根到叶子的路径代表一个关键词，用户输入前缀时先走到对应节点，再返回该节点维护的 TopK 关键词；为了省内存，可以用 radix tree、FST、共享字符串表或有序数组加二分查找。排序层不能只按字典序，要综合热度、近期点击、转化、业务权重、个性化和时效衰减；常见做法是在每个前缀节点预存 TopN keyword id，查询时直接取候选，再按实时特征重排。更新层要区分关键词库更新和热度更新：关键词新增删除可以离线构建新索引后原子切换，热度可以通过日志流增量更新热门前缀的 TopK 或放入 delta 索引，定期合并。内存控制上不要在每个节点存完整字符串和大列表，节点只存边、子节点引用和少量 top keyword id，关键词详情放字典表；热门前缀进本地缓存或 Redis。服务上要做输入归一化、长度限制、敏感词过滤、超时降级、空结果兜底、监控和压测。评估看 p95/p99 延迟、召回率、点击率、选择率、零结果率、更新延迟、内存占用和错误率。

考点 Trie/FST 召回

难度 真实面经题

回答目标 让面试官看到你能从数据结构走到可上线的搜索联想服务，覆盖召回、排序、更新、内存、延迟、风控和监控。

深入解析

前缀召回是第一层

关键词联想的基本查询是 prefix -> suggestions。Trie 很适合前缀匹配，因为查询复杂度主要取决于输入长度，而不是关键词总数。用户输入“中国”时，服务走到“中国”对应节点，再从这个节点拿候选，如“中国旅游”“中国银行”等。对于一百万关键词，单机内存通常可承载，但需要注意中文字符、大小写、全半角、空格和拼音等归一化策略。

内存结构要压缩

朴素 Trie 会产生大量节点和指针，内存可能膨胀。可以用压缩 Trie/radix tree 合并单分支路径，用 FST 做更紧凑的前缀自动机，用数组或 double-array trie 减少指针开销，也可以用排序后的关键词数组通过二分找到前缀区间。若主要需求是 TopK 热词，节点只需要保存少量 keyword id，不要存完整字符串和所有后代列表。

TopK 缓存决定查询速度

如果每次到前缀节点后都遍历整棵子树再排序，热门短前缀会非常慢。因此常见设计是在每个前缀节点预计算 TopN 关键词，查询时 O(prefix length + K) 返回。TopN 可以按热度、点击率、近期趋势、业务规则和质量分综合排序。短前缀节点访问量最大，应重点缓存；长尾前缀可以懒加载或回退到子树搜索。

排序要兼顾热度和质量

联想推荐不是纯数据结构题。排序分数可以包含全局搜索量、近期热度、点击率、选择率、转化、时效衰减、地域或用户个性化、关键词质量和风控过滤。热度过强会导致热门词长期霸榜，所以需要时间衰减和探索；个性化过强会增加缓存复杂度，通常可以先全局 TopK，再按用户上下文轻量重排。

更新分离离线全量和在线增量

关键词词库新增、删除、纠错可以离线构建新索引，校验后通过版本号原子切换，避免在线结构频繁变动导致锁竞争。热度变化更频繁，可以从搜索日志、点击日志或业务事件流生成增量分数，更新热门前缀的 TopK，或维护 delta index 与主索引合并。删除和敏感词下线要支持快速生效，可在过滤层或黑名单层兜底。

服务化要保证低延迟和可观测

线上服务需要多级缓存、超时控制、限流、降级和监控。热门前缀可以放进进程内 LRU 或 Redis，索引常驻内存，查询链路避免访问慢存储。监控 p50/p95/p99 延迟、QPS、错误率、缓存命中率、零结果率、返回数量、更新延迟和内存占用。压测要覆盖短前缀高并发、长前缀低命中、频繁更新和敏感词过滤。

易错点

只说用 Trie，不说明 TopK 如何维护、排序如何做、更新如何生效。
在每个节点存所有后代关键词或完整字符串，导致内存爆炸。
查询时临时遍历子树排序，短前缀高并发下延迟不可控。
只按字典序返回，不考虑热度、时效、点击反馈、质量和过滤规则。
把词库更新和热度更新混在一起，导致频繁重建索引或在线锁竞争。
忽略中文输入归一化、敏感词过滤、空结果、缓存击穿和 p99 延迟压测。

面试官追问

为什么不能每次查到前缀后遍历所有后代？

短前缀后代可能非常多，比如输入一个字就匹配大量关键词，遍历再排序会导致延迟不可控。预存每个前缀的 TopK 或 TopN 候选可以把查询变成近似常数时间返回。

Trie 和有序数组二分怎么取舍？

Trie 查询前缀自然，适合高 QPS 和节点 TopK 缓存，但内存开销较大。有序数组内存简单，可以二分找到前缀区间，但如果区间很大仍需扫描和排序。FST 或压缩 Trie 是性能和内存之间的折中。

热度实时变化怎么处理？

不要频繁重建整棵 Trie。可以用日志流更新关键词分数，对热门前缀的 TopK 做增量调整，或维护 delta 索引和主索引合并。周期性全量重建可以修正长期漂移。

如何做降级？

如果个性化重排或实时热度服务超时，可以返回前缀节点的全局 TopK；如果前缀无结果，可以缩短前缀、返回热门词或空结果。敏感词和黑名单过滤不能降级绕过。