跳到主要内容

设计搜索自动补全系统

问题​

如何设计一个高性能的搜索自动补全系统？从前端输入交互、Trie 前缀树、后端搜索服务到缓存策略与多数据源聚合，请详细说明核心模块的设计思路与关键技术实现。

答案​

搜索自动补全（Search Autocomplete / Typeahead）是搜索引擎、电商平台、内容站点等产品的核心交互组件。用户每输入一个字符，系统就需要在 100ms 以内 返回相关建议，同时兼顾 热词推荐、历史记录、模糊匹配 和 个性化排序。它的挑战在于：前端需要极致的输入体验（防抖、取消请求、键盘导航），后端需要在海量数据中做到毫秒级前缀检索。

核心设计原则

自动补全系统的本质是：在用户输入的极短窗口期内，从海量候选词中快速筛选并排序返回最相关的建议。所有架构设计都围绕"快"和"准"两个目标展开。

一、需求分析​

功能需求​

模块功能点
实时建议用户每次输入/删除字符后，实时展示匹配的搜索建议列表
热词推荐输入框聚焦但未输入时，展示热门搜索词
历史记录展示用户最近的搜索历史，支持删除单条和清空
模糊匹配支持拼音匹配、首字母匹配、容错纠错（如"javasript"→"javascript"）
分类聚合搜索建议来自多数据源（商品、用户、文章等），分组展示
高亮匹配搜索建议中高亮显示与用户输入匹配的文本片段
键盘导航支持上下键选择、Enter 确认、Esc 关闭

非功能需求​

指标目标
低延迟端到端响应时间 < 100ms（从输入到展示建议）
高并发支持百万级 QPS（每个用户每次输入都触发请求）
高可用服务降级策略：后端不可用时回退到本地历史/热词缓存
无障碍符合 WAI-ARIA Combobox 规范
移动端适配触控交互优化、虚拟键盘适配、带宽敏感
关键约束

自动补全是高频低延迟场景——用户打字速度约 5-10 字符/秒，每次按键都可能触发请求。通过防抖、缓存和请求取消等手段，可以将实际请求量降低 60%-80%。

二、整体架构​

2.1 架构全景​

2.2 数据流转​

三、核心模块设计​

3.1 前端实现​

3.1.1 防抖 + 取消请求​

搜索输入场景是防抖的经典应用。配合 AbortController 取消过时请求，避免竞态问题：

hooks/useSearchSuggest.ts
import { useState, useRef, useCallback, useEffect } from 'react';

interface SuggestItem {
  text: string;
  type: 'hot' | 'history' | 'product' | 'user' | 'article';
  highlight?: string;
}

interface UseSearchSuggestOptions {
  debounceMs?: number;
  maxResults?: number;
}

function useSearchSuggest(options: UseSearchSuggestOptions = {}) {
  const { debounceMs = 300, maxResults = 10 } = options;
  const [query, setQuery] = useState('');
  const [suggestions, setSuggestions] = useState<SuggestItem[]>([]);
  const [loading, setLoading] = useState(false);
  const [activeIndex, setActiveIndex] = useState(-1);

  const abortControllerRef = useRef<AbortController | null>(null);
  const timerRef = useRef<ReturnType<typeof setTimeout> | null>(null);
  const cacheRef = useRef(new LRUCache<string, SuggestItem[]>(50));

  const fetchSuggestions = useCallback(async (searchQuery: string) => {
    // 空查询返回热词
    if (!searchQuery.trim()) {
      const hotWords = await fetchHotWords();
      setSuggestions(hotWords);
      return;
    }

    // 检查前端 LRU 缓存
    const cached = cacheRef.current.get(searchQuery);
    if (cached) {
      setSuggestions(cached);
      return;
    }

    // 取消上一次未完成的请求
    if (abortControllerRef.current) {
      abortControllerRef.current.abort();
    }

    const controller = new AbortController();
    abortControllerRef.current = controller;

    setLoading(true);
    try {
      const response = await fetch(
        `/api/suggest?q=${encodeURIComponent(searchQuery)}&limit=${maxResults}`,
        { signal: controller.signal }
      );
      const data: SuggestItem[] = await response.json();

      // 写入缓存
      cacheRef.current.set(searchQuery, data);
      setSuggestions(data);
      setActiveIndex(-1);
    } catch (error) {
      // AbortError 是正常取消，不需处理
      if ((error as Error).name !== 'AbortError') {
        console.error('Suggest fetch failed:', error);
        // 降级：展示本地历史记录
        const history = getLocalHistory(searchQuery);
        setSuggestions(history);
      }
    } finally {
      setLoading(false);
    }
  }, [maxResults]);

  // 带防抖的输入处理
  const handleInputChange = useCallback((value: string) => {
    setQuery(value);
    if (timerRef.current) {
      clearTimeout(timerRef.current);
    }
    timerRef.current = setTimeout(() => {
      fetchSuggestions(value);
    }, debounceMs);
  }, [debounceMs, fetchSuggestions]);

  // 清理
  useEffect(() => {
    return () => {
      if (timerRef.current) clearTimeout(timerRef.current);
      if (abortControllerRef.current) abortControllerRef.current.abort();
    };
  }, []);

  return {
    query,
    suggestions,
    loading,
    activeIndex,
    setActiveIndex,
    handleInputChange,
  };
}
竞态问题

不使用 AbortController 时，如果用户快速输入 "ja" → "jav" → "java"，三个请求可能乱序返回，导致展示 "ja" 的结果覆盖 "java" 的结果。AbortController 确保只有最新请求的响应会被处理。

3.1.2 键盘导航​

hooks/useKeyboardNav.ts
interface UseKeyboardNavOptions {
  items: unknown[];
  activeIndex: number;
  setActiveIndex: (index: number) => void;
  onSelect: (index: number) => void;
  onEscape: () => void;
}

function useKeyboardNav({
  items,
  activeIndex,
  setActiveIndex,
  onSelect,
  onEscape,
}: UseKeyboardNavOptions) {

  const handleKeyDown = (e: React.KeyboardEvent) => {
    switch (e.key) {
      case 'ArrowDown':
        e.preventDefault();
        setActiveIndex(
          activeIndex < items.length - 1 ? activeIndex + 1 : 0
        );
        break;
      case 'ArrowUp':
        e.preventDefault();
        setActiveIndex(
          activeIndex > 0 ? activeIndex - 1 : items.length - 1
        );
        break;
      case 'Enter':
        e.preventDefault();
        if (activeIndex >= 0) {
          onSelect(activeIndex);
        }
        break;
      case 'Escape':
        onEscape();
        break;
    }
  };

  return { handleKeyDown };
}

3.1.3 高亮匹配文本​

utils/highlight.tsx
import React from 'react';

/** 将搜索词在文本中高亮显示 */
function highlightMatch(text: string, query: string): React.ReactNode {
  if (!query.trim()) return text;

  // 转义正则特殊字符
  const escaped = query.replace(/[.*+?^${}()|[\]\\]/g, '\\$&');
  const regex = new RegExp(`(${escaped})`, 'gi');
  const parts = text.split(regex);

  return (
    <>
      {parts.map((part, index) =>
        regex.test(part) ? (
          <mark key={index} className="suggest-highlight">{part}</mark>
        ) : (
          <span key={index}>{part}</span>
        )
      )}
    </>
  );
}

3.1.4 无障碍（ARIA Combobox）​

搜索自动补全组件必须遵循 WAI-ARIA Combobox 模式，确保屏幕阅读器用户也能正常使用：

components/SearchAutocomplete.tsx
function SearchAutocomplete() {
  const {
    query, suggestions, loading, activeIndex,
    setActiveIndex, handleInputChange,
  } = useSearchSuggest();

  const listboxId = 'search-suggestions-listbox';
  const inputId = 'search-input';

  return (
    <div role="combobox" aria-expanded={suggestions.length > 0} aria-haspopup="listbox" aria-owns={listboxId}>
      <input
        id={inputId}
        type="text"
        role="searchbox"
        aria-autocomplete="list"
        aria-controls={listboxId}
        aria-activedescendant={
          activeIndex >= 0 ? `suggestion-${activeIndex}` : undefined
        }
        value={query}
        onChange={(e) => handleInputChange(e.target.value)}
        placeholder="搜索..."
      />

      {suggestions.length > 0 && (
        <ul id={listboxId} role="listbox" aria-label="搜索建议">
          {suggestions.map((item, index) => (
            <li
              key={index}
              id={`suggestion-${index}`}
              role="option"
              aria-selected={index === activeIndex}
              className={index === activeIndex ? 'active' : ''}
              onMouseEnter={() => setActiveIndex(index)}
            >
              {highlightMatch(item.text, query)}
              <span className="suggest-type">{item.type}</span>
            </li>
          ))}
        </ul>
      )}

      {loading && <div aria-live="polite">加载中...</div>}
    </div>
  );
}
ARIA 属性作用
role="combobox"标识组合框组件
aria-expanded告知列表是否展开
aria-autocomplete="list"表明有自动补全列表
aria-activedescendant标识当前活跃的选项
aria-selected标识选中状态
aria-live="polite"加载状态变化时通知屏幕阅读器

3.2 Trie 前缀树​

Trie（发音 /traɪ/，来源于 retrieval）是自动补全的核心数据结构。它通过共享前缀来高效存储和检索字符串。

3.2.1 数据结构​

3.2.2 TypeScript 实现​

data-structures/Trie.ts
interface TrieNode {
  children: Map<string, TrieNode>;
  isEnd: boolean;        // 是否是完整词
  word: string;          // 完整词（仅 isEnd=true 时有值）
  weight: number;        // 权重（搜索频次）
}

class Trie {
  private root: TrieNode;

  constructor() {
    this.root = this.createNode();
  }

  private createNode(): TrieNode {
    return {
      children: new Map(),
      isEnd: false,
      word: '',
      weight: 0,
    };
  }

  /** 插入词条及其权重 */
  insert(word: string, weight: number = 1): void {
    let node = this.root;
    for (const char of word.toLowerCase()) {
      if (!node.children.has(char)) {
        node.children.set(char, this.createNode());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
    node.word = word;
    node.weight += weight;
  }

  /** 搜索前缀，返回按权重排序的 Top-K 结果 */
  suggest(prefix: string, topK: number = 10): Array<{ word: string; weight: number }> {
    let node = this.root;
    for (const char of prefix.toLowerCase()) {
      if (!node.children.has(char)) {
        return []; // 前缀不存在
      }
      node = node.children.get(char)!;
    }

    // DFS 收集所有以该前缀开头的词
    const results: Array<{ word: string; weight: number }> = [];
    this.dfs(node, results);

    // 按权重降序排序，取 Top-K
    return results
      .sort((a, b) => b.weight - a.weight)
      .slice(0, topK);
  }

  private dfs(
    node: TrieNode,
    results: Array<{ word: string; weight: number }>
  ): void {
    if (node.isEnd) {
      results.push({ word: node.word, weight: node.weight });
    }
    for (const child of node.children.values()) {
      this.dfs(child, results);
    }
  }

  /** 删除词条 */
  delete(word: string): boolean {
    return this.deleteHelper(this.root, word.toLowerCase(), 0);
  }

  private deleteHelper(node: TrieNode, word: string, index: number): boolean {
    if (index === word.length) {
      if (!node.isEnd) return false;
      node.isEnd = false;
      node.word = '';
      node.weight = 0;
      return node.children.size === 0;
    }

    const char = word[index];
    const child = node.children.get(char);
    if (!child) return false;

    const shouldDelete = this.deleteHelper(child, word, index + 1);
    if (shouldDelete) {
      node.children.delete(char);
      return !node.isEnd && node.children.size === 0;
    }
    return false;
  }
}

3.2.3 Trie 复杂度分析​

操作时间复杂度说明
插入O(L)O(L)LL 为词的长度
精确搜索O(L)O(L)逐字符匹配
前缀搜索O(L+N)O(L + N)LL 为前缀长度，NN 为匹配结果数
空间复杂度O(C×L×N)O(C \times L \times N)CC 为字符集大小，LL 为平均词长，NN 为词条数
优化方向

生产环境中，Trie 常结合以下优化：

  • 压缩 Trie（Radix Tree）：合并只有单个子节点的路径，减少空间
  • Top-K 预计算：每个节点预存 Top-K 结果，避免每次搜索都 DFS
  • 双数组 Trie（DAT）：用数组替代 Map，提升缓存命中率

3.3 后端搜索服务​

3.3.1 Elasticsearch Completion Suggester​

Elasticsearch 内置了 Completion Suggester，专为自动补全场景优化。它在索引时构建 FST（有限状态转换器），查询时直接在内存中完成前缀匹配，延迟极低。

services/ElasticSuggestService.ts
import { Client } from '@elastic/elasticsearch';

interface SuggestResult {
  text: string;
  score: number;
  source: string;
}

class ElasticSuggestService {
  private client: Client;

  constructor() {
    this.client = new Client({ node: 'http://localhost:9200' });
  }

  /** 创建索引（含 completion 字段） */
  async createIndex(): Promise<void> {
    await this.client.indices.create({
      index: 'suggestions',
      body: {
        mappings: {
          properties: {
            suggest: {
              type: 'completion',   // Completion Suggester 专用类型
              analyzer: 'simple',
              contexts: [           // 上下文过滤
                { name: 'category', type: 'category' },
              ],
            },
            weight: { type: 'integer' },
          },
        },
      },
    });
  }

  /** 索引一条建议 */
  async indexSuggestion(
    text: string,
    weight: number,
    category: string
  ): Promise<void> {
    await this.client.index({
      index: 'suggestions',
      body: {
        suggest: {
          input: [text],
          weight,
          contexts: { category: [category] },
        },
      },
    });
  }

  /** 查询建议 */
  async suggest(
    prefix: string,
    category?: string,
    size: number = 10
  ): Promise<SuggestResult[]> {
    const body: Record<string, unknown> = {
      suggest: {
        'search-suggest': {
          prefix,
          completion: {
            field: 'suggest',
            size,
            skip_duplicates: true,
            fuzzy: {
              fuzziness: 'AUTO',  // 自动模糊匹配（容错纠错）
            },
            ...(category && {
              contexts: { category: [category] },
            }),
          },
        },
      },
    };

    const response = await this.client.search({
      index: 'suggestions',
      body,
    });

    const suggestions = (response as any).suggest['search-suggest'][0].options;
    return suggestions.map((opt: any) => ({
      text: opt.text,
      score: opt._score,
      source: opt._source,
    }));
  }
}

3.3.2 Redis 缓存层​

services/RedisCacheService.ts
import Redis from 'ioredis';

class SuggestCacheService {
  private redis: Redis;
  private readonly TTL = 300; // 5 分钟过期

  constructor() {
    this.redis = new Redis({ host: 'localhost', port: 6379 });
  }

  /** 缓存 key 规则：suggest:{prefix} */
  private getCacheKey(prefix: string): string {
    return `suggest:${prefix.toLowerCase()}`;
  }

  /** 读缓存 */
  async get(prefix: string): Promise<SuggestResult[] | null> {
    const key = this.getCacheKey(prefix);
    const cached = await this.redis.get(key);
    return cached ? JSON.parse(cached) : null;
  }

  /** 写缓存 */
  async set(prefix: string, results: SuggestResult[]): Promise<void> {
    const key = this.getCacheKey(prefix);
    await this.redis.setex(key, this.TTL, JSON.stringify(results));
  }

  /** 热词排行榜（Sorted Set） */
  async recordSearch(keyword: string): Promise<void> {
    const now = Date.now();
    // ZINCRBY 增加搜索计数
    await this.redis.zincrby('hot:keywords', 1, keyword);
    // 记录最后搜索时间（用于时间衰减）
    await this.redis.hset('hot:timestamps', keyword, now.toString());
  }

  /** 获取热词 Top-K */
  async getHotKeywords(topK: number = 10): Promise<string[]> {
    // ZREVRANGE 按分数降序取
    return this.redis.zrevrange('hot:keywords', 0, topK - 1);
  }
}

3.4 热词排序算法​

搜索建议的排序需要综合多个维度，而不仅仅是搜索频次：

services/RankingService.ts
interface RankingFactors {
  searchFrequency: number;  // 搜索频次
  lastSearchTime: number;   // 最后搜索时间戳
  clickRate: number;        // 点击率
  isPersonalized: boolean;  // 是否个性化推荐
}

/**
 * 综合排序公式：
 * score = frequency * timeDecay * clickBoost * personalBoost
 */
function calculateScore(factors: RankingFactors): number {
  const {
    searchFrequency,
    lastSearchTime,
    clickRate,
    isPersonalized,
  } = factors;

  const now = Date.now();
  const hoursSinceLastSearch = (now - lastSearchTime) / (1000 * 60 * 60);

  // 时间衰减：越久远的搜索权重越低（指数衰减）
  // 半衰期设为 24 小时
  const timeDecay = Math.pow(0.5, hoursSinceLastSearch / 24);

  // 点击率加成
  const clickBoost = 1 + clickRate;

  // 个性化加成
  const personalBoost = isPersonalized ? 1.5 : 1;

  return searchFrequency * timeDecay * clickBoost * personalBoost;
}

/** 对搜索建议列表重新排序 */
function rankSuggestions(
  suggestions: Array<{ text: string; factors: RankingFactors }>
): string[] {
  return suggestions
    .map((item) => ({
      text: item.text,
      score: calculateScore(item.factors),
    }))
    .sort((a, b) => b.score - a.score)
    .map((item) => item.text);
}
排序因子说明
因子权重影响来源
搜索频次基础分值搜索日志聚合
时间衰减越近越高最后搜索时间戳
点击率有效性指标用户点击/曝光比
个性化1.5x 加成用户画像匹配
地域区域热门IP / GPS 定位
季节/时事临时加权运营配置

四、关键技术实现​

4.1 搜索历史​

services/LocalHistoryService.ts
const HISTORY_KEY = 'search_history';
const MAX_HISTORY = 20;

interface HistoryItem {
  keyword: string;
  timestamp: number;
}

class LocalHistoryService {
  /** 添加搜索记录 */
  static add(keyword: string): void {
    const history = this.getAll();

    // 去重：如果已存在，先删除旧的
    const filtered = history.filter((item) => item.keyword !== keyword);

    // 添加到头部
    filtered.unshift({ keyword, timestamp: Date.now() });

    // 限制数量
    const trimmed = filtered.slice(0, MAX_HISTORY);

    localStorage.setItem(HISTORY_KEY, JSON.stringify(trimmed));
  }

  /** 获取全部历史 */
  static getAll(): HistoryItem[] {
    try {
      const raw = localStorage.getItem(HISTORY_KEY);
      return raw ? JSON.parse(raw) : [];
    } catch {
      return [];
    }
  }

  /** 按前缀过滤历史 */
  static search(prefix: string): HistoryItem[] {
    return this.getAll().filter((item) =>
      item.keyword.toLowerCase().startsWith(prefix.toLowerCase())
    );
  }

  /** 删除单条 */
  static remove(keyword: string): void {
    const history = this.getAll().filter((item) => item.keyword !== keyword);
    localStorage.setItem(HISTORY_KEY, JSON.stringify(history));
  }

  /** 清空全部 */
  static clear(): void {
    localStorage.removeItem(HISTORY_KEY);
  }
}

4.2 拼音搜索​

中文搜索场景下，用户可能输入拼音或拼音首字母来搜索中文内容：

services/PinyinSearchService.ts
// 使用 pinyin-pro 库
import { pinyin, match as pinyinMatch } from 'pinyin-pro';

interface PinyinSearchItem {
  text: string;
  pinyinFull: string;    // 全拼：javascript -> javascript, 手机 -> shouji
  pinyinInitial: string; // 首字母：手机 -> sj
}

class PinyinSearchService {
  private items: PinyinSearchItem[] = [];

  /** 预处理：为每个词条生成拼音索引 */
  buildIndex(words: string[]): void {
    this.items = words.map((text) => ({
      text,
      pinyinFull: pinyin(text, { toneType: 'none', type: 'array' }).join(''),
      pinyinInitial: pinyin(text, { pattern: 'initial', type: 'array' }).join(''),
    }));
  }

  /** 搜索：同时匹配原文、全拼、首字母 */
  search(query: string, topK: number = 10): string[] {
    const lowerQuery = query.toLowerCase();

    return this.items
      .filter((item) => {
        // 原文匹配
        if (item.text.toLowerCase().includes(lowerQuery)) return true;
        // 全拼匹配
        if (item.pinyinFull.includes(lowerQuery)) return true;
        // 首字母匹配
        if (item.pinyinInitial.includes(lowerQuery)) return true;
        // pinyin-pro 的智能匹配（支持混合输入如 "shou机"）
        if (pinyinMatch(item.text, query)) return true;
        return false;
      })
      .slice(0, topK)
      .map((item) => item.text);
  }
}

// 使用示例
const service = new PinyinSearchService();
service.buildIndex(['手机', '手表', '电脑', '耳机', 'iPhone']);

service.search('sj');    // ['手机']
service.search('shou');  // ['手机', '手表']
service.search('shou机'); // ['手机']

4.3 多数据源聚合​

电商等场景下，搜索建议需要同时展示商品、品牌、分类、用户等多种类型的结果：

services/AggregateService.ts
interface SuggestGroup {
  type: 'product' | 'brand' | 'category' | 'user' | 'article';
  label: string;
  items: Array<{ text: string; meta?: string; icon?: string }>;
}

interface DataSource {
  type: SuggestGroup['type'];
  label: string;
  search: (query: string, limit: number) => Promise<SuggestGroup['items']>;
  priority: number;  // 展示优先级
  maxItems: number;  // 每个数据源最多展示条数
}

class AggregateService {
  private sources: DataSource[] = [];

  registerSource(source: DataSource): void {
    this.sources.push(source);
    // 按优先级排序
    this.sources.sort((a, b) => a.priority - b.priority);
  }

  /** 并发查询所有数据源，聚合结果 */
  async search(query: string): Promise<SuggestGroup[]> {
    const results = await Promise.allSettled(
      this.sources.map(async (source) => {
        const items = await source.search(query, source.maxItems);
        return {
          type: source.type,
          label: source.label,
          items,
        } as SuggestGroup;
      })
    );

    // 过滤失败的请求，只返回成功的
    return results
      .filter(
        (r): r is PromiseFulfilledResult<SuggestGroup> =>
          r.status === 'fulfilled' && r.value.items.length > 0
      )
      .map((r) => r.value);
  }
}

// 使用示例
const aggregator = new AggregateService();

aggregator.registerSource({
  type: 'product',
  label: '商品',
  priority: 1,
  maxItems: 5,
  search: async (query, limit) => {
    const res = await fetch(`/api/products/suggest?q=${query}&limit=${limit}`);
    return res.json();
  },
});

aggregator.registerSource({
  type: 'brand',
  label: '品牌',
  priority: 2,
  maxItems: 3,
  search: async (query, limit) => {
    const res = await fetch(`/api/brands/suggest?q=${query}&limit=${limit}`);
    return res.json();
  },
});

4.4 前端 LRU 缓存​

自动补全的前端缓存是性能优化的关键一环。用户在搜索过程中频繁输入和删除字符，很多前缀会被重复查询。关于 LRU 缓存的详细原理，可参考手写 LRU 缓存。

utils/LRUCache.ts
class LRUCache<K, V> {
  private capacity: number;
  private cache: Map<K, V>;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key: K): V | undefined {
    if (!this.cache.has(key)) return undefined;

    // 访问后移到末尾（最近使用）
    const value = this.cache.get(key)!;
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  set(key: K, value: V): void {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // 删除最久未使用的（Map 的第一个元素）
      const firstKey = this.cache.keys().next().value;
      if (firstKey !== undefined) {
        this.cache.delete(firstKey);
      }
    }
    this.cache.set(key, value);
  }

  has(key: K): boolean {
    return this.cache.has(key);
  }

  clear(): void {
    this.cache.clear();
  }
}

五、性能优化​

5.1 多级缓存策略​

缓存层级介质TTL命中率延迟
L1：前端 LRU内存（JS Map）会话内有效~30%~0ms
L2：CDN 边缘CDN 节点1-5 分钟~40%~10ms
L3：Redis内存5-30 分钟~25%~20ms
L4：Elasticsearch磁盘 + 内存 FST实时兜底~50ms
缓存穿透防护

对于查无结果的前缀，也需要缓存空结果（短 TTL），防止大量无效请求打到 ES。可以用 Bloom Filter 做前置判断——如果 Bloom Filter 判断前缀一定不存在，则直接返回空。

5.2 请求优化策略​

策略说明效果
防抖用户停止输入 200-300ms 后才发请求减少 60%-80% 请求
最小查询长度输入至少 2 个字符才触发请求减少无意义的短前缀请求
取消旧请求AbortController 取消上一次未完成请求避免竞态、节省带宽
前缀复用"jav" 的结果可用于过滤 "java" 的本地结果减少网络请求
批量预取用户输入 "j" 时预取 "ja"、"je"、"ji" 等高频后续提升后续输入速度

前缀复用的实现思路：

utils/prefixReuse.ts
/**
 * 前缀复用：如果新查询是旧查询的延伸，
 * 直接在旧结果中过滤，无需请求后端
 */
function tryLocalFilter(
  newQuery: string,
  prevQuery: string,
  prevResults: SuggestItem[]
): SuggestItem[] | null {
  // 新查询必须以旧查询为前缀
  if (!newQuery.startsWith(prevQuery) || prevQuery.length === 0) {
    return null;
  }

  // 在旧结果中过滤
  return prevResults.filter((item) =>
    item.text.toLowerCase().startsWith(newQuery.toLowerCase())
  );
}

5.3 移动端适配​

问题解决方案
虚拟键盘弹出遮挡建议列表监听 visualViewport resize，动态调整列表位置
触控 vs 鼠标touchstart 替代 hover，增大点击区域（至少 44px）
带宽有限增大防抖延迟（400-500ms），减少 maxResults
输入法组合输入监听 compositionstart / compositionend，组合输入期间不触发搜索
hooks/useCompositionInput.ts
import { useState, useCallback, useRef } from 'react';

/** 处理中文输入法组合输入 */
function useCompositionInput(onSearch: (value: string) => void) {
  const [value, setValue] = useState('');
  const isComposingRef = useRef(false);

  const handleCompositionStart = useCallback(() => {
    isComposingRef.current = true;
  }, []);

  const handleCompositionEnd = useCallback(
    (e: React.CompositionEvent<HTMLInputElement>) => {
      isComposingRef.current = false;
      // 组合输入结束后触发搜索
      onSearch((e.target as HTMLInputElement).value);
    },
    [onSearch]
  );

  const handleChange = useCallback(
    (e: React.ChangeEvent<HTMLInputElement>) => {
      const newValue = e.target.value;
      setValue(newValue);
      // 组合输入期间不触发搜索
      if (!isComposingRef.current) {
        onSearch(newValue);
      }
    },
    [onSearch]
  );

  return {
    value,
    handleChange,
    handleCompositionStart,
    handleCompositionEnd,
  };
}

六、扩展设计​

6.1 纠错与模糊匹配​

方案原理适用场景
编辑距离（Levenshtein）计算两个字符串的最小编辑操作数"javasript" → "javascript"
N-gram将字符串拆分为 N 个字符的子串进行匹配部分匹配
Soundex / Metaphone基于发音的模糊匹配英文拼写纠错
ES Fuzzy Query基于编辑距离的模糊查询后端通用方案

6.2 搜索建议的 A/B 测试​

services/ABTestService.ts
interface ABTestConfig {
  experimentId: string;
  variants: Array<{
    id: string;
    weight: number;               // 流量分配权重
    config: {
      debounceMs: number;
      maxResults: number;
      enableFuzzy: boolean;
      enablePersonalized: boolean;
      rankingAlgorithm: 'frequency' | 'timeDecay' | 'ml';
    };
  }>;
}

/** 根据用户 ID 分配实验组（哈希取模） */
function assignVariant(
  userId: string,
  config: ABTestConfig
): ABTestConfig['variants'][0] {
  const hash = simpleHash(userId + config.experimentId);
  const totalWeight = config.variants.reduce((sum, v) => sum + v.weight, 0);
  let target = hash % totalWeight;

  for (const variant of config.variants) {
    target -= variant.weight;
    if (target < 0) return variant;
  }

  return config.variants[0];
}

function simpleHash(str: string): number {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    const char = str.charCodeAt(i);
    hash = ((hash << 5) - hash) + char;
    hash = hash & hash; // 转为 32 位整数
  }
  return Math.abs(hash);
}

6.3 系统监控指标​

指标计算方式目标值
P99 响应时间从输入到展示建议的端到端延迟< 100ms
建议点击率（CTR）点击建议次数 / 建议展示次数> 30%
缓存命中率缓存命中次数 / 总请求次数> 90%
空结果率返回空建议次数 / 总请求次数< 5%
请求取消率被 AbortController 取消次数 / 总请求次数观察值

常见面试问题​

Q1: 如何实现高性能的自动补全系统？​

答案：

高性能自动补全需要前后端协同优化，从数据结构、缓存、网络请求三个维度入手：

1. 数据结构层面——Trie 前缀树 + 预计算 Top-K

data-structures/OptimizedTrie.ts
interface OptimizedTrieNode {
  children: Map<string, OptimizedTrieNode>;
  isEnd: boolean;
  word: string;
  weight: number;
  topK: Array<{ word: string; weight: number }>; // 预计算的 Top-K 结果
}

class OptimizedTrie {
  private root: OptimizedTrieNode;
  private k: number;

  constructor(k: number = 10) {
    this.root = this.createNode();
    this.k = k;
  }

  private createNode(): OptimizedTrieNode {
    return { children: new Map(), isEnd: false, word: '', weight: 0, topK: [] };
  }

  /**
   * 插入时沿途更新每个节点的 topK
   * 这样查询时直接返回节点的 topK，无需 DFS
   * 查询复杂度从 O(L+N) 降为 O(L)
   */
  insert(word: string, weight: number): void {
    let node = this.root;
    for (const char of word.toLowerCase()) {
      if (!node.children.has(char)) {
        node.children.set(char, this.createNode());
      }
      node = node.children.get(char)!;
      // 更新路径上每个节点的 topK
      this.updateTopK(node, word, weight);
    }
    node.isEnd = true;
    node.word = word;
    node.weight = weight;
  }

  private updateTopK(
    node: OptimizedTrieNode,
    word: string,
    weight: number
  ): void {
    const existing = node.topK.findIndex((item) => item.word === word);
    if (existing !== -1) {
      node.topK[existing].weight = weight;
    } else {
      node.topK.push({ word, weight });
    }
    node.topK.sort((a, b) => b.weight - a.weight);
    if (node.topK.length > this.k) {
      node.topK.pop();
    }
  }

  /** 查询只需遍历前缀字符，直接返回 topK，O(L) */
  suggest(prefix: string): Array<{ word: string; weight: number }> {
    let node = this.root;
    for (const char of prefix.toLowerCase()) {
      if (!node.children.has(char)) return [];
      node = node.children.get(char)!;
    }
    return node.topK;
  }
}

2. 缓存层面——多级缓存

层级策略效果
前端 LRU缓存最近 50 个查询结果重复输入零延迟
CDN 边缘热门前缀静态化全球低延迟
RedisSorted Set 存储热词毫秒级响应
ES FST内存中的有限状态转换器海量数据前缀匹配

3. 网络层面——减少和加速请求

  • 防抖 300ms，减少 70% 请求
  • AbortController 取消过时请求
  • 前缀复用——"java" 的结果可从 "jav" 的缓存中本地过滤
  • HTTP/2 多路复用，减少连接开销

Q2: Trie 前缀树和倒排索引有什么区别？分别适用于什么场景？​

答案：

维度Trie 前缀树倒排索引
数据结构树形结构，每个节点代表一个字符词 → 文档 ID 列表的映射表
查询类型前缀匹配（"jav" → "java", "javascript"）全文搜索（包含某个词的所有文档）
时间复杂度查询 O(L)O(L)，LL 为前缀长度查询 O(1)O(1) 查词 + O(N)O(N) 合并结果
空间消耗较大（每个字符一个节点）较小（只存词和文档 ID）
适用场景自动补全、拼写检查、IP 路由搜索引擎、日志检索、全文检索
典型实现内存 Trie、Redis 有序集合Elasticsearch、Lucene
实时性插入即可查询需要重建索引（近实时）
面试关键点

两者不是互斥的，生产环境通常结合使用：

  • Elasticsearch 的 Completion Suggester 内部使用 FST（类似压缩 Trie）做前缀补全
  • 用户选中补全词后，再用倒排索引做全文搜索

Q3: 如何处理高并发搜索请求？​

答案：

自动补全是典型的读多写少场景，高并发优化策略分为四个层面：

1. 客户端限流

客户端限流策略
// 防抖：300ms 内只发最后一次请求
const debouncedSearch = debounce(fetchSuggestions, 300);

// 最小查询长度：至少 2 个字符
function handleInput(value: string): void {
  if (value.length < 2) {
    setSuggestions([]);
    return;
  }
  debouncedSearch(value);
}

// 前缀复用：在本地缓存中过滤
function smartFetch(query: string): void {
  const cached = tryLocalFilter(query, prevQuery, prevResults);
  if (cached && cached.length >= 3) {
    // 本地结果足够，不请求后端
    setSuggestions(cached);
    return;
  }
  fetchFromServer(query);
}

2. CDN + 边缘计算

  • 将 Top 1000 热门前缀的结果缓存到 CDN
  • 边缘节点直接返回，不回源
  • 热词列表每 5 分钟刷新

3. 服务端架构

策略实现效果
Redis 缓存前缀 → 结果的 KV 缓存命中率 90%+
限流令牌桶 / 滑动窗口保护下游服务
降级ES 不可用时回退到 Redis 热词保证可用性
水平扩展Suggest Service 无状态，支持水平扩容线性提升吞吐

4. 数据分片

数据分片策略
/**
 * 按首字母分片：将词条分布到不同的 Trie 实例
 * 每个分片由独立的服务实例负责
 */
function getShardId(prefix: string, totalShards: number): number {
  const firstChar = prefix.charAt(0).toLowerCase();
  const charCode = firstChar.charCodeAt(0);
  return charCode % totalShards;
}

// 路由层根据前缀首字母路由到对应分片
async function routeToShard(prefix: string): Promise<SuggestResult[]> {
  const shardId = getShardId(prefix, 26);
  const shardHost = `suggest-shard-${shardId}.internal`;
  const response = await fetch(`http://${shardHost}/suggest?q=${prefix}`);
  return response.json();
}

Q4: 防抖和节流在搜索场景中怎么选择？​

答案：

搜索自动补全应该使用防抖（Debounce），而不是节流（Throttle）。两者的核心区别如下：

特性防抖（Debounce）节流（Throttle）
触发时机用户停止输入一段时间后触发固定时间间隔内最多触发一次
搜索场景表现用户打完字才搜索，结果精准打字过程中也会搜索，中间结果无意义
请求量最少（只在停顿时触发）较多（持续输入时定期触发）
用户体验等待感稍强，但结果更准反馈更快，但结果可能不精准
防抖 vs 节流对比
// 用户输入 "javascript"（假设每 100ms 输入一个字符）

// 防抖 300ms：
// j(0ms) → a(100ms) → v(200ms) → a(300ms) → s(400ms)
// → c(500ms) → r(600ms) → i(700ms) → p(800ms) → t(900ms)
// → [停止输入] → 1200ms 触发请求 "javascript"
// 结果：只发 1 次请求 ✓

// 节流 300ms：
// j(0ms) → 触发 "j"
// → a(100ms) → v(200ms) → a(300ms) → 触发 "java"
// → s(400ms) → c(500ms) → r(600ms) → 触发 "javascr"
// → i(700ms) → p(800ms) → t(900ms) → 触发 "javascript"
// 结果：发了 4 次请求，前 3 次都是"废请求" ✗
最佳实践
  • 搜索自动补全：使用防抖（300ms），等用户停止输入后再搜索
  • 滚动加载更多：使用节流（200ms），滚动过程中定期检查
  • 窗口 resize：使用防抖（150ms），调整完成后重新计算布局
  • 实时协同编辑：使用节流（500ms），定期同步内容

更详细的防抖与节流对比，可参考防抖和节流。

相关链接​