设计搜索自动补全系统

在搜索框中打字，会展示一个或更多的与搜索词匹配的结果。这个功能叫 自动补全、提前输入、边输边搜、增量搜索。

最简单的方法

假设有一个频率表，有连个字段

• query 查询，用于存储查询字符串
• frequency 频次，表示某个查询词被搜索过的次数

当用户在搜索框中输入，进行前缀匹配，假设将5个被频繁搜索的查询词展示给用户。

为了获取搜索频率排在前5位的5个查询词，可以用 SQL

SELECT * FROM frequency_table
WHERE query LIKE `prefix%`
ORDER BY frequency DESC
LIMIT 5;

当数据集较小，这是一个可以接受的方案，但当数据集很大时，数据库访问会成为一个瓶颈。

字典树数据结构

字典树也叫前缀树。

• 字典树是一个树状数据结构
• 根节点表示一个空字符串
• 每个节点存储一个字符，共有26个节点，每个字节点对应一个可能的字符
• 每个树节点表示一个单词或一个前缀字符串

其中单词后面的数字是频率。

进行一些设定：

• p：前缀的长度
• n：字典树中节点的总数
• c：给定节点的字节点数

算法的时间复杂度 O(p) + O(c) + O(clogc)

O(p) 是前缀长度 也就是到 tr 节点， O(c) 是 tr 节点下面有c个叶子节点，以便获取叶子， O(clogc) 是要进行排序频率。

最坏情况下，需要遍历整个字典树才能获取排名前k的结果。

可以限制前缀的最大长度、在每个节点缓存被高频搜索的查询词。

数据收集服务

无论用户何时输入查询词，字典树中的数据都会时时更新。

• 用户可能每天输入输十亿个查询词，对每个查询词都更新字典树会显著降低查询服务的速度
• 一旦字典树被创建，对高频查询词的建议可能不会经常变化，因此，没有必要频繁更新字典树

用来构建字典树的数据通常都来自数据分析服务或者日志服务记录。

更新频率要看具体的业务。

字典树缓存：用分布式缓存系统，把字典树保存在内存缓存按周期获取一次数据的快照。

字典树数据库：

1. 文档存储，将字典树序列化然后数据存在MongoDB之类的文档数据库
2. 键值存储，字典树可以通过一定逻辑用哈希表形式表示

查询服务

1. 查询请求发送给负载均衡器
2. 负载均衡器把请求转发给API服务器
3. API服务器从字典树缓存中读取字典树数据，构建建议数据返回给客户端
4. 如果数据不在字典树缓存中，将数据填充回缓存，之后如果有相同前缀的查询请求，可以从缓存中获取返回结果

字典树操作

创建，通过 Worker 使用聚合数据（统计好的有频率信息）创建，数据源头是数据分析日志或数据库

更新，按周期创建新字典树新的替代老的，或者直接更新单个字典树节点（操作慢应避免使用），如下面图 把 beer 频率更新为30

删除，如仇恨暴力色情危险内容应该删除，在字典树缓存之前加一个过滤层，过滤不想要的建议。

扩展存储

字典树太大可能无法放在单个服务器上。

一个简单的方法是根据查询词的第一个字符来做分片。如 a-m n-z 放在两台服务器上。

如果字典树更大，则可能还需要进行二级分片，aa-ag ah-an ao-au av-az 放在多台服务器上。

但是c开头的词比x开头的多很多，回导致数据分布不均衡。加一个分片映射管理器维护一个查找数据库，用来确定数据应该被存储在哪个分片上。