系统设计：如何设计搜索自动补全（搜索建议）系统

在搜索框输入“跑步”，下拉立刻提示“跑步鞋男”“跑步机家用”“跑步袜”——这就是自动补全（Autocomplete / Typeahead）。它的核心挑战是：每次击键都要在几十毫秒内，从海量词条中找出“以当前输入为前缀、且最热门”的前 K 条。

一、需求与约束

输入前缀 p，返回以 p 开头的查询建议 Top-K（K 通常 5~10）；
建议按热度排序（搜索量、点击率、转化率），而非简单字典序；
极低延迟：用户每敲一个字符就触发一次请求，要求 P99 < 50~100ms；
高 QPS（搜索是最高频入口之一）；
支持中文（需分词/拼音）、个性化（结合用户历史）、容错（错别字）。

二、核心数据结构：Trie（字典树/前缀树）

前缀匹配的天然结构是 Trie：从根到某节点的路径代表一个前缀，共享前缀的词共用同一条路径。查“跑步”的所有候选，就是走到“跑步”节点，再遍历它的子树。

flowchart TB
    Root(("根")) --> P["跑"]
    P --> B["步"]
    P --> D["道"]
    B --> X["鞋"]
    B --> J["机"]
    B --> W["袜"]
    X --> X1["鞋男 (热度 9800)"]
    X --> X2["鞋女 (热度 7200)"]
    J --> J1["机家用 (热度 5100)"]
    W --> W1["袜 (热度 3300)"]

但朴素 Trie 有两个问题：

遍历整棵子树再排序太慢：“跑”下面可能挂着几十万个词，每次都遍历 + 排序无法满足几十毫秒；
内存占用大（每个字符一个节点）。

解法：在每个节点预存 Top-K 热门候选。

构建 Trie 时，为每个节点维护一个容量为 K 的小顶堆，只保留经过该前缀的、最热的 K 个词。这样查询时走到对应节点，直接拿到已排好序的 Top-K，无需遍历子树，复杂度约等于前缀长度 O(len(p))。

词典通常百万级词条，Trie 常驻内存（或用压缩 Trie / Radix Tree 省空间），单机即可扛住大部分查询；
节点存的是候选词的 ID/引用 + 热度，而非完整字符串。

三、热度从哪来：离线构建

建议的热度不是拍脑袋的，而是从历史搜索日志统计出来的。整套系统分离线和在线两部分：

flowchart TB
    subgraph Offline["离线（定期构建）"]
        Log["搜索/点击日志"] --> Agg["统计词频与热度<br/>（搜索量 + 点击率加权）"]
        Agg --> Dict["生成热门词典<br/>过滤低频/违规词"]
        Dict --> Trie["构建 Trie<br/>每节点预计算 Top-K"]
        Trie --> Snap["生成数据快照"]
    end
    Snap --> Online
    subgraph Online["在线（低延迟查询）"]
        Req["用户输入前缀"] --> Cache{"缓存命中？"}
        Cache -- 是 --> Ret["返回建议"]
        Cache -- 否 --> T2["查内存 Trie 取 Top-K"]
        T2 --> Rank["个性化/业务规则重排"]
        Rank --> Ret
    end

离线用 Spark 等聚合日志，统计每个查询词的热度（可加入时间衰减，让新词、突发热点上位）；
过滤低频词、违禁词，只保留 Top 百万级热门词构建 Trie；
生成快照后推送到在线服务内存，定时（如每天/每小时）更新，热加载不中断服务。

四、在线服务：极致低延迟

内存查询：Trie 常驻进程内存，查询不走磁盘、不查数据库，微秒级；
多级缓存：热门前缀（如“跑”“手机”）的结果放 Redis 甚至本地缓存，命中率极高——因为用户输入高度集中在少数热词；
前端防抖 + 边缘加速：输入停顿才发请求（debounce），结果可经 CDN/边缘节点缓存；
服务无状态水平扩展，Trie 快照在每个实例各持一份（词典不大，全量复制比分片更简单）。

五、中文、个性化与容错

中文/拼音：中文没有空格，需对词条做分词，或同时建“汉字 Trie + 拼音 Trie”，输入“paobu”也能出“跑步”；
个性化重排：在通用热度基础上，结合用户画像（性别、地域、历史搜索）对 Top-K 做轻量重排——例如同样是“跑步鞋”，给男性用户优先“男款”；
容错/模糊：对错别字可在 Trie 之外加编辑距离匹配，或借助搜索引擎的模糊召回兜底；
纯前缀覆盖不到的长尾，可回退到 Elasticsearch 的 edge-ngram 前缀索引做补充。

六、方案对比

方案	优点	缺点	适用
内存 Trie + 节点 Top-K	极快、可控	需构建、占内存	热门词前缀建议（主流）
Redis ZSET	实现简单、可分片	网络开销、词多时慢	中小规模快速上线
ES edge-ngram	功能强、支持模糊/分词	延迟相对高、成本高	长尾兜底、复杂搜索