构建高性能全文搜索引擎：倒排索引、BM25 排序与混合检索完整实现

Google 每天处理 85 亿次搜索查询，平均响应时间仅 0.38 秒。背后支撑这一切的，是倒排索引（Inverted Index）和 BM25 排序算法这两项核心技术。对于开发者而言，理解搜索引擎的底层原理不仅能帮你优化应用的搜索体验，更能让你在构建 RAG、推荐系统等 AI 应用时做出更明智的架构决策。

本文将从零构建一个支持中文分词、BM25 排序和向量混合检索的完整搜索引擎，所有代码均可直接运行。

🔍 一、核心数据结构：倒排索引的构建与优化

1.1 倒排索引的基本原理

正排索引（Forward Index）是「文档 → 词」的映射，而倒排索引是「词 → 文档列表」的映射。这是搜索引擎能实现毫秒级查询的关键。

正排索引：
  文档1: "TypeScript 类型系统很强大"
  文档2: "JavaScript 是动态类型语言"

倒排索引：
  "TypeScript"  → [文档1]
  "类型"        → [文档1, 文档2]
  "系统"        → [文档1]
  "JavaScript"  → [文档2]
  "动态"        → [文档2]

1.2 完整的倒排索引实现

// 倒排索引核心实现
interface PostingEntry {
  docId: number;
  termFrequency: number;  // 词频
  positions: number[];     // 词位置（用于短语搜索）
}

interface IndexDocument {
  id: number;
  title: string;
  content: string;
  [key: string]: unknown;
}

class InvertedIndex {
  // term → PostingEntry[]
  private index = new Map<string, PostingEntry[]>();
  // docId → 文档元信息
  private documents = new Map<number, IndexDocument>();
  // docId → 文档长度（词数）
  private docLengths = new Map<number, number>();
  // 总文档数
  private totalDocs = 0;
  // 所有文档的平均长度
  private avgDocLength = 0;
  // 总词数（用于计算平均长度）
  private totalTerms = 0;

  // 添加文档到索引
  addDocument(doc: IndexDocument): void {
    const docId = doc.id;
    this.documents.set(docId, doc);
    this.totalDocs++;

    // 合并标题和内容进行索引
    const text = `${doc.title} ${doc.content}`;
    const tokens = this.tokenize(text);

    this.docLengths.set(docId, tokens.length);
    this.totalTerms += tokens.length;
    this.avgDocLength = this.totalTerms / this.totalDocs;

    // 统计每个词的出现位置
    const termPositions = new Map<string, number[]>();
    tokens.forEach((token, position) => {
      const positions = termPositions.get(token) || [];
      positions.push(position);
      termPositions.set(token, positions);
    });

    // 构建 posting list
    termPositions.forEach((positions, term) => {
      const postings = this.index.get(term) || [];
      postings.push({
        docId,
        termFrequency: positions.length,
        positions,
      });
      this.index.set(term, postings);
    });
  }

  // 分词器（支持中文和英文）
  tokenize(text: string): string[] {
    // 简单的中文分词：按字符 + 英文单词分割
    const normalized = text.toLowerCase().replace(/[^\w\u4e00-\u9fff]/g, ' ');
    const tokens: string[] = [];
    const segments = normalized.split(/\s+/).filter(Boolean);

    for (const segment of segments) {
      // 英文单词直接作为 token
      if (/^[a-z0-9]+$/.test(segment)) {
        tokens.push(segment);
        continue;
      }
      // 中文按 bigram 分词（生产环境应使用 jieba 等分词库）
      for (let i = 0; i < segment.length - 1; i++) {
        if (/[\u4e00-\u9fff]/.test(segment[i])) {
          tokens.push(segment.substring(i, i + 2));
        }
      }
      // 中文单字也作为 token（提高召回率）
      for (const char of segment) {
        if (/[\u4e00-\u9fff]/.test(char)) {
          tokens.push(char);
        }
      }
    }
    return tokens;
  }

  // 获取某个 term 的 posting list
  getPostings(term: string): PostingEntry[] {
    return this.index.get(term.toLowerCase()) || [];
  }

  // 获取文档长度
  getDocLength(docId: number): number {
    return this.docLengths.get(docId) || 0;
  }

  // 获取平均文档长度
  getAvgDocLength(): number {
    return this.avgDocLength;
  }

  // 获取总文档数
  getTotalDocs(): number {
    return this.totalDocs;
  }

  // 获取包含某 term 的文档数（用于 IDF 计算）
  getDocFrequency(term: string): number {
    return this.getPostings(term).length;
  }

  // 获取文档
  getDocument(docId: number): IndexDocument | undefined {
    return this.documents.get(docId);
  }
}

📌 记住： 生产环境的中文分词必须使用专业分词库（如 jieba、nodejieba），bigram 分词只适合演示。分词质量直接影响搜索准确率，差距可达 30% 以上。

1.3 Posting List 的压缩优化

当文档量达到百万级时，Posting List 的存储成为瓶颈。以下是两种常用的压缩策略：

// VByte 编码实现
function vbyteEncode(numbers: number[]): Uint8Array {
  const bytes: number[] = [];
  for (const num of numbers) {
    let value = num;
    const temp: number[] = [];
    temp.push(value & 0x7f);
    value >>>= 7;
    while (value > 0) {
      temp.push((value & 0x7f) | 0x80);
      value >>>= 7;
    }
    bytes.push(...temp.reverse());
  }
  return new Uint8Array(bytes);
}

function vbyteDecode(data: Uint8Array): number[] {
  const result: number[] = [];
  let current = 0;
  let shift = 0;
  for (const byte of data) {
    current = (current << 7) | (byte & 0x7f);
    shift += 7;
    if ((byte & 0x80) === 0) {
      result.push(current);
      current = 0;
      shift = 0;
    }
  }
  return result;
}

// 压缩效果对比
const testData = Array.from({ length: 100000 }, (_, i) => i);
const raw = new TextEncoder().encode(JSON.stringify(testData));
const compressed = vbyteEncode(testData);
console.log(`原始大小: ${(raw.length / 1024).toFixed(1)} KB`);
console.log(`VByte 压缩后: ${(compressed.length / 1024).toFixed(1)} KB`);
console.log(`压缩率: ${((1 - compressed.length / raw.length) * 100).toFixed(1)}%`);

📊 二、BM25 排序算法：从 TF-IDF 到生产级评分

2.1 BM25 算法原理

BM25（Best Matching 25）是目前最广泛使用的文本相关性排序算法，Elasticsearch、Lucene 的默认评分都基于 BM25。它在 TF-IDF 的基础上做了三个关键改进：

1. 词频饱和：词频增长到一定程度后，贡献递减（避免某个词重复出现 100 次就排在最前面）
2. 文档长度归一化：长文档天然包含更多词，需要惩罚
3. 可调参数：通过 k1 和 b 参数控制词频饱和度和长度归一化强度

BM25 公式：
                IDF(qi) · tf(qi, D) · (k1 + 1)
Score(Q, D) = Σ ──────────────────────────────────
                tf(qi, D) + k1 · (1 - b + b · |D|/avgdl)

其中：
  IDF(qi) = ln((N - n(qi) + 0.5) / (n(qi) + 0.5) + 1)
  N     = 总文档数
  n(qi) = 包含词 qi 的文档数
  tf    = 词 qi 在文档 D 中的词频
  |D|   = 文档 D 的长度
  avgdl = 所有文档的平均长度
  k1    = 词频饱和参数（通常 1.2-2.0）
  b     = 长度归一化参数（通常 0.75）

2.2 BM25 完整实现

class BM25Scorer {
  private k1: number;
  private b: number;

  constructor(k1 = 1.2, b = 0.75) {
    this.k1 = k1;
    this.b = b;
  }

  // 计算 IDF（逆文档频率）
  private idf(totalDocs: number, docFreq: number): number {
    return Math.log((totalDocs - docFreq + 0.5) / (docFreq + 0.5) + 1);
  }

  // 计算单个 query term 对文档的评分
  scoreTerm(
    termFrequency: number,  // 词在文档中的出现次数
    docLength: number,       // 文档长度
    avgDocLength: number,    // 平均文档长度
    totalDocs: number,       // 总文档数
    docFreq: number,         // 包含该词的文档数
  ): number {
    const idf = this.idf(totalDocs, docFreq);
    const tfNorm = (termFrequency * (this.k1 + 1)) /
      (termFrequency + this.k1 * (1 - this.b + this.b * docLength / avgDocLength));
    return idf * tfNorm;
  }

  // 计算查询对文档的总评分
  scoreDocument(
    queryTerms: string[],
    index: InvertedIndex,
    docId: number,
  ): number {
    let score = 0;
    const docLength = index.getDocLength(docId);
    const avgDocLength = index.getAvgDocLength();
    const totalDocs = index.getTotalDocs();

    for (const term of queryTerms) {
      const postings = index.getPostings(term);
      const posting = postings.find(p => p.docId === docId);
      if (!posting) continue;

      const docFreq = postings.length;
      score += this.scoreTerm(
        posting.termFrequency,
        docLength,
        avgDocLength,
        totalDocs,
        docFreq,
      );
    }
    return score;
  }
}

💡 提示： k1 参数控制词频饱和速度。k1=0 时完全忽略词频（纯 IDF 排序），k1 越大越依赖词频。英文场景推荐 k1=1.2，中文场景可适当提高到 1.5-2.0，因为中文分词后单个 token 的信息密度较低。

2.3 BM25 与 TF-IDF 性能对比

我们用 10,000 篇模拟文档进行基准测试：

⚡ 关键结论： BM25 相比 TF-IDF 在相关性排序上有显著优势，额外的计算开销几乎可以忽略。在 2026 年，没有任何理由继续使用原始 TF-IDF。

🚀 三、混合检索：BM25 + 向量检索的融合策略

3.1 为什么需要混合检索？

纯 BM25 只能处理字面匹配，无法理解语义。例如搜索「如何提升网站速度」，BM25 找不到包含「优化页面加载性能」的文档。纯向量检索擅长语义匹配，但在精确匹配（如搜索产品编号 SKU-2024-001）上表现不佳。

混合检索（Hybrid Search）结合两者优势，是 2026 年生产级搜索系统的标配。

// 混合检索核心实现
interface SearchResult {
  docId: number;
  score: number;
  document: IndexDocument | undefined;
  matchType: 'bm25' | 'vector' | 'hybrid';
}

class HybridSearchEngine {
  private index: InvertedIndex;
  private bm25: BM25Scorer;
  // 模拟向量索引（生产环境应使用 hnswlib-node 或 pgvector）
  private vectorIndex = new Map<number, number[]>();
  private embeddingFn: (text: string) => Promise<number[]>;

  constructor(embeddingFn: (text: string) => Promise<number[]>) {
    this.index = new InvertedIndex();
    this.bm25 = new BM25Scorer();
    this.embeddingFn = embeddingFn;
  }

  async addDocument(doc: IndexDocument): Promise<void> {
    this.index.addDocument(doc);
    // 生成文档向量并存储
    const text = `${doc.title} ${doc.content}`;
    const vector = await this.embeddingFn(text);
    this.vectorIndex.set(doc.id, vector);
  }

  // 余弦相似度计算
  private cosineSimilarity(a: number[], b: number[]): number {
    let dotProduct = 0, normA = 0, normB = 0;
    for (let i = 0; i < a.length; i++) {
      dotProduct += a[i] * b[i];
      normA += a[i] * a[i];
      normB += b[i] * b[i];
    }
    return dotProduct / (Math.sqrt(normA) * Math.sqrt(normB) || 1);
  }

  // BM25 搜索
  bm25Search(query: string, topK = 10): SearchResult[] {
    const queryTerms = this.index.tokenize(query);
    const candidateDocs = new Set<number>();

    // 收集所有包含查询词的文档
    for (const term of queryTerms) {
      for (const posting of this.index.getPostings(term)) {
        candidateDocs.add(posting.docId);
      }
    }

    // 评分并排序
    const results: SearchResult[] = [];
    for (const docId of candidateDocs) {
      const score = this.bm25.scoreDocument(queryTerms, this.index, docId);
      results.push({
        docId,
        score,
        document: this.index.getDocument(docId),
        matchType: 'bm25',
      });
    }

    results.sort((a, b) => b.score - a.score);
    return results.slice(0, topK);
  }

  // 向量搜索
  async vectorSearch(query: string, topK = 10): Promise<SearchResult[]> {
    const queryVector = await this.embeddingFn(query);
    const results: SearchResult[] = [];

    for (const [docId, docVector] of this.vectorIndex) {
      const score = this.cosineSimilarity(queryVector, docVector);
      results.push({
        docId,
        score,
        document: this.index.getDocument(docId),
        matchType: 'vector',
      });
    }

    results.sort((a, b) => b.score - a.score);
    return results.slice(0, topK);
  }

  // 混合检索：Reciprocal Rank Fusion (RRF)
  async hybridSearch(
    query: string,
    topK = 10,
    options: { bm25Weight?: number; vectorWeight?: number; rrfK?: number } = {},
  ): Promise<SearchResult[]> {
    const { rrfK = 60 } = options;

    // 并行执行 BM25 和向量搜索
    const [bm25Results, vectorResults] = await Promise.all([
      this.bm25Search(query, topK * 3),  // 取更多候选
      this.vectorSearch(query, topK * 3),
    ]);

    // Reciprocal Rank Fusion 融合
    const scores = new Map<number, number>();

    bm25Results.forEach((result, rank) => {
      const current = scores.get(result.docId) || 0;
      scores.set(result.docId, current + 1 / (rrfK + rank + 1));
    });

    vectorResults.forEach((result, rank) => {
      const current = scores.get(result.docId) || 0;
      scores.set(result.docId, current + 1 / (rrfK + rank + 1));
    });

    // 排序并返回
    const merged: SearchResult[] = [];
    for (const [docId, score] of scores) {
      merged.push({
        docId,
        score,
        document: this.index.getDocument(docId),
        matchType: 'hybrid',
      });
    }

    merged.sort((a, b) => b.score - a.score);
    return merged.slice(0, topK);
  }
}

⚠️ 警告： 不要对 BM25 分数和向量相似度分数直接加权求和！两者的分数量纲完全不同（BM25 分数无上界，向量相似度在 [-1, 1] 之间），直接相加会导致结果不可控。Reciprocal Rank Fusion（RRF）只依赖排名不依赖分数，是更稳健的融合策略。

3.2 RRF vs 加权求和 vs ColBERT 重排序

在实际项目中，推荐采用两阶段检索架构：

1. 第一阶段（召回）：BM25 + 向量检索混合召回 Top-100 候选
2. 第二阶段（精排）：用 Cross-Encoder 或 ColBERT 对候选集重新排序

这种架构在延迟和效果之间取得了最佳平衡。

3.3 端到端使用示例

// 完整的搜索引擎使用示例
async function demo() {
  // 模拟 embedding 函数（生产环境使用 OpenAI / BGE / E5 等模型）
  const mockEmbedding = async (text: string): Promise<number[]> => {
    const hash = Array.from(text).reduce((h, c) => ((h << 5) - h + c.charCodeAt(0)) | 0, 0);
    return Array.from({ length: 128 }, (_, i) => Math.sin(hash * (i + 1)));
  };

  const engine = new HybridSearchEngine(mockEmbedding);

  // 添加文档
  const documents = [
    { id: 1, title: 'TypeScript 入门教程', content: 'TypeScript 是 JavaScript 的超集，添加了静态类型系统' },
    { id: 2, title: 'Python 数据分析', content: '使用 Pandas 和 NumPy 进行高效数据处理和分析' },
    { id: 3, title: 'React 性能优化', content: '使用 React.memo 和 useMemo 优化组件渲染性能' },
    { id: 4, title: 'JavaScript 类型系统', content: '了解 JavaScript 的动态类型特性与 TypeScript 的静态类型对比' },
    { id: 5, title: '前端构建工具对比', content: 'Vite、Rspack 和 Turbopack 的性能对比与选型建议' },
  ];

  for (const doc of documents) {
    await engine.addDocument(doc);
  }

  // BM25 搜索
  console.log('=== BM25 搜索: "TypeScript 类型" ===');
  const bm25Results = engine.bm25Search('TypeScript 类型');
  for (const r of bm25Results) {
    console.log(`  [${r.score.toFixed(3)}] ${r.document?.title}`);
  }

  // 混合搜索
  console.log('\n=== 混合搜索: "静态类型语言" ===');
  const hybridResults = await engine.hybridSearch('静态类型语言');
  for (const r of hybridResults) {
    console.log(`  [${r.score.toFixed(4)}] (${r.matchType}) ${r.document?.title}`);
  }
}

demo();

💡 四、生产级搜索引擎的工程实践

4.1 索引更新策略

生产环境的索引不能停机重建。以下是三种常见的更新策略：

Elasticsearch 采用的就是「近实时索引」策略：文档先写入内存 Buffer，每 1 秒 refresh 到新的 Segment，后台异步合并小 Segment。这个设计在实时性和写入性能之间取得了很好的平衡。

4.2 搜索质量优化清单

• ✅ 使用专业中文分词库：jieba / pkuseg / LAC，不要用 bigram
• ✅ 配置同义词词典：「手机」↔「移动电话」↔「智能手机」
• ✅ 实现搜索纠错：编辑距离 + 拼音相似度
• ✅ 添加停用词过滤：「的」「了」「是」等高频无意义词
• ✅ 支持搜索高亮：返回匹配片段并标记命中词
• ❌ 不要忽略大小写和全半角：统一做 normalization
• ❌ 不要在索引阶段做 stemming：应在查询阶段做（避免索引信息丢失）
• ⚠️ 注意分词粒度：太细导致噪音，太粗导致召回不足

4.3 性能基准测试

在 10 万篇文档（平均每篇 500 词）的数据集上测试：

💡 提示： 如果查询延迟超过 10ms，优先检查是否使用了内存索引而非磁盘索引。对于百万级文档，建议使用 FST（Finite State Transducer）存储词典，内存占用可降低 60%。

📌 总结与工具推荐

构建生产级搜索引擎的核心要点：

1. 倒排索引是基础：理解 Posting List 的存储和压缩是优化查询性能的关键
2. BM25 是标配：不要再用原始 TF-IDF，BM25 在所有场景下都更优
3. 混合检索是趋势：BM25 精确匹配 + 向量语义理解，用 RRF 融合
4. 分词决定上限：中文搜索的质量 80% 取决于分词质量

推荐工具和库：

对于大多数项目，我的建议是：小规模（< 10 万文档）用 SQLite FTS5，中等规模用 MeiliSearch 或 Typesense，大规模用 Elasticsearch。 不要过度设计——如果你的搜索需求可以用 LIKE '%keyword%' 满足，那就不要上搜索引擎。但当你的用户开始抱怨「搜不到」的时候，就是引入 BM25 + 向量混合检索的最佳时机。