倒排索引原理与 Elasticsearch 应用

🎯 面试题：什么是倒排索引？为什么 Elasticsearch 查询这么快？

倒排索引是搜索引擎的核心数据结构，与传统正排索引相反，通过「词 → 文档列表」的方式实现快速检索。本题考察对全文检索底层原理的理解深度。

一、正排索引 vs 倒排索引

正排索引（Forward Index）：
  文档1 → [词1, 词2, 词3, 词4]
  文档2 → [词2, 词3, 词5, 词6]
  
  查包含"词3"的文档：需要遍历所有文档
  
倒排索引（Inverted Index）：
  词1 → [文档1]
  词2 → [文档1, 文档2]
  词3 → [文档1, 文档2]
  
  查包含"词3"的文档：直接查词3的列表 → [文档1, 文档2]

二、倒排索引结构

倒排索引 = Term Dictionary + Posting List

┌────────────────────────────────────────────────────┐
│ Term Dictionary（词典）                              │
│  ┌──────────┐ ┌──────────┐ ┌──────────┐          │
│  │  阿     │ │  里     │ │  巴     │  ← 词项   │
│  │ (指针)  │ │ (指针)  │ │ (指针)  │          │
│  └──────────┘ └──────────┘ └──────────┘          │
│        ↓            ↓            ↓                │
│ ┌────────────────────────────────────────────┐   │
│ │ Posting List（倒排列表）                     │   │
│ │                                            │   │
│ │ 词 "阿里" → docID[1,3,7], freq[2,1,3],    │   │
│ │            position[0,2][1,0][0,4,6]      │   │
│ │                                            │   │
│ │ 每个元素的格式：                            │   │
│ │ [docID(文档ID), freq(出现次数),            │   │
│ │  [position1, position2...](词出现位置)]  │   │
│ └────────────────────────────────────────────┘   │
└────────────────────────────────────────────────────┘

三、FST 压缩

Finite State Transducer

FST（有限状态自动机）：压缩 Term Dictionary

普通词典：
  阿里 → 0x1234
  阿里巴巴 → 0x5678
  阿里云 → 0x9ABC

FST 压缩：
      ┌──A──┐
  ──→○──L──○──I──○──B──○── (阿里) → 0x1234
            │
           (N──○──B──○──U──○── (阿里巴巴) → 0x5678
            │
            (U──○──N──○── (阿里云) → 0x9ABC

FST 优势：
  - 共享前缀，节省空间（可减少 80% 词典体积）
  - 有序存储，支持二分查找
  - 支持前缀查询（自动补全）

四、分词器原理

分词流程：

原始文本："Spring Boot 框架非常强大"
         ↓
┌──────────────────────────────────┐
│ 1. 字符过滤器（Character Filter）   │
│    - HTML 标签去除               │
│    - 特殊字符过滤               │
└──────────────────────────────────┘
         ↓
┌──────────────────────────────────┐
│ 2. 分词器（Tokenizer）           │
│    - 按空格/标点切分             │
│    - Spring / Boot / 框架 / 非常 / 强大 │
└──────────────────────────────────┘
         ↓
┌──────────────────────────────────┐
│ 3. Token Filter（词项过滤器）    │
│    - 转小写（Spring → spring）   │
│    - 词干提取（frameworks → framework）│
│    - 同义词扩展                  │
└──────────────────────────────────┘
         ↓
    spring, boot, 框架, 非常, 强大

五、ES 内置分词器

PUT /my_index
{
  "settings": {
    "analyzer": {
      "my_analyzer": {
        "type": "custom",
        "tokenizer": "standard",
        "filter": ["lowercase", "stop", "snowball"]
      }
    }
  }
}

GET /_analyze
{
  "analyzer": "standard",
  "text": "Spring Boot's power"
}
→ [spring, boot, power]

GET /_analyze
{
  "analyzer": "ik_max_word",
  "text": "Java后端面试指南"
}
→ [java, 后端, 面试, 指南]

六、查询流程

ES 查询流程（三个阶段）：

第一阶段：parse（解析）
  用户查询 → DSL 解析 → 抽象语法树
  
第二阶段：rewrite（重写）+ score（打分）
  - 根据路由找到对应 shard
  - 每个 shard 查询本地倒排索引
  - 计算 TF/IDF/BM25 相关性得分

第三阶段：fetch（获取）
  - 协调节点收集所有 shard 结果
  - 按得分排序
  - 取 top N 文档
  - 从各 shard 拉取完整文档

┌─────────────────────────────────────────────┐
│              协调节点（Coordinating Node）   │
│                                             │
│  Query Phase：                               │
│  ┌─────┐ ┌─────┐ ┌─────┐                   │
│  │Shrad│ │Shrad│ │Shrad│                   │
│  │  0  │ │  1  │ │  2  │                   │
│  └──┬──┘ └──┬──┘ └──┬──┘                   │
│     │        │        │                      │
│  收集 Top100 排序    收集 Top100 排序    │
│     │        │        │                      │
│     └────────┼────────┘                      │
│              ↓                               │
│         汇总 Top N                           │
│              ↓                               │
│  Fetch Phase：                               │
│  ┌─────────────────────────────────────┐    │
│  │ 并行从各 shard 拉取文档内容          │    │
│  └─────────────────────────────────────┘    │
│              ↓                               │
│         返回给用户                          │
└─────────────────────────────────────────────┘

七、面试高频题

Q1: 倒排索引是什么？它和正排索引的区别是什么？

正排索引是「文档 → 词」的映射，查询时需要遍历所有文档。倒排索引是「词 → 文档列表」的映射，查询时直接查词的列表，性能高几个数量级。倒排索引包含 Term Dictionary（词典，有序存储所有词）和 Posting List（倒排列表，记录每个词出现在哪些文档中）。Elasticsearch 使用 FST 对词典进行压缩，支持前缀查询。

Q2: Elasticsearch 查询为什么这么快？

三个原因：① 倒排索引：词到文档的映射是 O(1) 查询，而非遍历；② FST 压缩词典：词典有序且共享前缀，占用内存小，可完全加载到内存；③ 分布式架构：数据分片到多个节点并行查询，横向扩展。核心是倒排索引 + 内存缓存 + 分片并行。

Q3: 分词器有哪些类型？如何选择？

ES 内置分词器：standard（默认，英文分词）、simple（按非字母切分）、whitespace（按空格切分）、keyword（不分词，整体作为一个词）、pattern（正则分词）。中文推荐 IK（ik_max_word 细粒度、ik_smart 粗粒度）或 jieba。分词器选择影响召回率和精确率：粗粒度召回率高但精确率低，细粒度精确率高但召回率低。