Elasticsearch-实现原理

一、Elasticsearch 与传统数据库对比

1.1 关键点概览

1. 文档模型（Document-Oriented）
   - Elasticsearch 视每条记录为一个文档（JSON 格式）。
   - 一个索引（Index）下可包含多个文档，索引底层又被分为一个或多个分片（Shard），每个分片是一个独立的 Lucene 索引。
2. 分布式 & 可扩展性
   - 通过自动拆分（Sharding）与副本（Replica）机制，支持大规模数据的分布式存储和并行搜索。
   - 可通过增加/减少节点进行水平扩展。
3. 近实时搜索（NRT）
   - ES 提供近实时写入与搜索能力：文档写入后经内存缓冲，再定期刷新到段文件，查询时几乎能够及时检索到新数据。
4. 灵活的查询与分析
   - 支持全文检索、复合查询、聚合分析（类似于 SQL 的 GROUP BY，但实现原理不同），并可利用多种分析器处理不同语言或数据类型。

1.2 与 MySQL（InnoDB）对比

• InnoDB 采用 B+ 树（或其变体）作为索引结构，适合基于主键或索引字段进行精确或范围查询；在处理大规模文本检索时效率相对较低。
• Elasticsearch（底层基于 Lucene）核心采用 倒排索引（Inverted Index） 进行全文搜索，对多关键词的搜索场景尤其高效。

在谈论 Elasticsearch 与传统关系型数据库（如 MySQL InnoDB）的存储结构差异时，最核心的区别在于：

• MySQL（InnoDB）主要使用 B+ 树（或其变体）来组织行数据，方便按主键或索引字段进行查找。
• Elasticsearch（底层基于 Lucene）则使用倒排索引（Inverted Index）来进行高效的全文检索和结构化查询。

下面分几个方面说明 Elasticsearch 的关键点、倒排索引的实现原理、存储结构，以及为什么查询快。

---

1. Elasticsearch 的关键点

1. 文档模型（Document-Oriented）
   - Elasticsearch 将每条记录看作一个文档（Document），文档以 JSON 格式保存。
   - 一个索引（Index）包含多个文档，底层又被拆分为一个或多个分片（Shard），每个分片就是一个独立的 Lucene 索引。
2. 分布式 & 可扩展性
   - 通过自动拆分和副本机制，支持大规模数据存储与检索。
   - 水平扩展能力强，可以在集群中增减节点，自动平衡存储与查询负载。
3. 实时搜索
   - 新增或更新文档后，Lucene 会快速将数据写入一个内存缓冲区，随后段文件（segment）合并异步进行；一旦写入到新段，就能对外提供近实时的搜索。
4. 灵活的查询与分析
   - 除了全文检索，还支持多种复合查询、聚合分析（类似数据库中的 GROUP BY，但实现原理不同）等功能。

---

二、倒排索引（Inverted Index）原理

2.1 什么是倒排索引

• 正排索引（Forward Index）：记录“每个文档中包含哪些词”。
• 倒排索引（Inverted Index）：记录“每个词出现在哪些文档里”，并往往还包含该词在文档中的位置、词频等信息。

在搜索“keyword1 AND keyword2”时，倒排索引只需分别找到这两个词对应的文档列表，并做交集即可，远快于逐行扫描所有数据。

倒排索引的概念

• 正排索引（Forward Index）

：每个文档有哪些词。例如：

doc1: ["elasticsearch", "fast", "search"] doc2: ["mysql", "innodb", "b+tree"] ...

• 倒排索引（Inverted Index）

：每个词出现在哪些文档里。例如：

"elasticsearch": [doc1] "fast": [doc1] "search": [doc1] "mysql": [doc2] "innodb": [doc2] ...

在搜索 “fast AND search” 时，可以快速得到 [doc1] 的交集，然后立即定位到匹配文档。

倒排索引的结构

以 Lucene 为例，倒排索引的核心数据结构可拆分为两部分：

1. 词典（Term Dictionary）：保存每个唯一词（term）的有序列表，并且可以通过前缀或二分搜索快速定位到对应词的位置。Lucene 里一般用 FST（Finite State Transducer） 来压缩并存储这个词典。

2. 倒排表（Posting List）

：存储每个词在哪些文档（docID）中出现，以及在文档中的位置、出现次数等。

• 形式可以理解为：

  term -> [ (docID1, positions...), (docID2, positions...), ... ]

• 文档 ID、词频、词位置等信息可以进一步压缩与编码，以减少存储体积和 I/O。

2.2 Lucene 中的倒排索引结构

1. 词典（Term Dictionary）

• 存储索引中所有唯一词（term）的有序列表，常使用 FST（Finite State Transducer）进行压缩存储。
• 通过前缀搜索、二分搜索等可快速定位到目标词在索引中的位置。

2. 倒排表（Posting List）

• 记录该词出现在哪些文档（docID）中，以及在文档中的位置、出现次数等信息。

• 形式可理解为：

  term -> [ (docID1, positions...), (docID2, positions...), ... ]

• 这些 docID 和位置信息一般还会采用各种编码/压缩以减少存储空间、提升检索速度。

2.3 Elasticsearch 数据存储结构

• Segment（段文件）
• Lucene 索引会被切分为多个 segment，每个 segment 存储了该段数据的倒排索引、存储字段、DocValues 等，写入后只读。
• 文档更新/删除并不会直接修改现有段文件，而是追加到新 segment 或进行标记，最后通过 Segment Merge 进行合并与优化。
• Stored Fields
• 用于存储原始文档的字段值（通常以压缩形式）。
• DocValues
• 列式存储，用来支持聚合、排序等场景，减少检索整个文档字段的开销。
• 近实时（NRT）
• Lucene 通过写入内存缓冲、定时刷新到新 segment，再对外可见，实现数据的近实时可搜。

2.4 为什么 Elasticsearch 查询速度快

1. 倒排索引
   - 在多关键词搜索场景下，按倒排表做交集远比传统逐行匹配或基于 B+ 树的文本搜索要高效。
2. 段文件 + FST
   - 大规模词典通过 FST 压缩存储，大幅节省空间，且可快速定位单词对应的倒排表。
3. DocValues
   - 列式存储在排序与聚合时能减少大量 IO。
4. 分布式并行搜索
   - 多分片（Shard）可并行搜索，查询延迟大幅降低。

---

三、FST（Finite State Transducer）字典

3.1 背景与动机

在全文检索场景中，可能存在数百万乃至上亿不重复词（term）。若采用朴素的数据结构（如哈希表、B 树）存储这些单词，内存占用非常大，查询效率也会受影响。于是引入 FST 来在前缀层面进行最大化压缩，同时保持对单词的快速查找能力。

3.2 FST 的核心原理

1. Trie（字典树）共享前缀
   - 把所有单词的公共前缀合并在一条路径上，减少重复节点。
2. DAG（Directed Acyclic Graph）压缩
   - 若不同单词分支的后缀完全相同，可将这些节点进一步合并，形成有向无环图结构，显著节约空间。
3. Transducer（转换器）
   - 在状态机节点中携带输出值（如倒排表偏移量等），到达路径终点即可获取相应数据。
4. 高效查找
   - 对海量单词进行排序后再构建 FST，可实现前缀查询、精确词查询等操作时的快速定位，且压缩率极高。

3.3 FST 在 Lucene/Elasticsearch 中的应用

• 主要用于 Term Dictionary 的存储与快速检索：对分词后产生的海量唯一词进行紧凑化处理，并支持高效前缀搜索、精确匹配定位到倒排列表。

---

四、同时支持中文分词与拼音查询

在中文搜索环境中，有时用户不仅会输入汉字，也会通过拼音来搜索某些内容。要兼容这两种方式，常见做法是给同一个逻辑字段配置多种分词方式（多字段/multi-fields），分别使用 中文分词（IK） 和 拼音分析器（analysis-pinyin）。

4.1 多字段 (multi-fields) 配置

示例 Mapping（仅供参考，需视插件与版本可能略有不同）：

PUT my_index
{
  "settings": {
    "analysis": {
      "analyzer": {
        "ik_smart_analyzer": {
          "type": "custom",
          "tokenizer": "ik_smart"
        },
        "pinyin_analyzer": {
          "type": "custom",
          "tokenizer": "pinyin",
          "filter": [
            "lowercase"
            // 如果需要模糊拼音匹配，可加 nGram filter 等
          ]
        }
      }
    }
  },
  "mappings": {
    "properties": {
      "name": {
        "type": "text",
        "fields": {
          "ik": {
            "type": "text",
            "analyzer": "ik_smart_analyzer",
            "search_analyzer": "ik_smart_analyzer"
          },
          "pinyin": {
            "type": "text",
            "analyzer": "pinyin_analyzer",
            "search_analyzer": "pinyin_analyzer"
          }
        }
      }
    }
  }
}

这样同一个字段 name 会产生两个子字段：

• name.ik：中文分词索引
• name.pinyin：拼音分词索引

4.2 查询方式

1. multi_match 查询

json GET my_index/_search { "query": { "multi_match": { "query": "zhangsan", "fields": ["name.ik^1", "name.pinyin^2"] } } }

• 同时匹配 name.ik 和 name.pinyin，并可调整各自的权重。

2. Bool should 查询

json GET my_index/_search { "query": { "bool": { "should": [ { "match": { "name.ik": "张三" }}, { "match": { "name.pinyin": "zhangsan" }} ] } } }

• 在“should”子句里分别写中文、拼音匹配，只要匹配到其中之一即可返回结果。

4.3 模糊拼音 / 部分拼音查询

若需要支持用户仅输入拼音首字母（如 zs 搜“张三”），可以在拼音分析器中添加 nGram 或 edge nGram：

"filter": [
  "lowercase",
  {
    "type": "ngram",
    "min_gram": 1,
    "max_gram": 5
  }
]

这样会将 zhangsan 拆成 z, zh, zha, zhan, zhang, ... 等多种 token，从而支持更灵活的前缀/模糊匹配。但需注意索引体量、写入和搜索性能的影响。

4.4 注意与优化

1. 插件兼容性
   - IK 与 analysis-pinyin 插件版本需与 ES 对应。
2. 索引体量与写性能
   - 多一种分析方式，就会多一份倒排索引；结合 nGram 会产生更多 token，索引空间增大。
3. 搜索性能
   - 并行检索多个字段也会带来额外的 CPU、IO 开销。
4. 灵活使用多字段
   - 除 IK、pinyin 外，也可配置只索引首字母（initials）等子字段，用于更快速的首字母搜索。

---

五、总结

1. Elasticsearch 与 InnoDB
   - 前者适合全文检索，大规模文本与多关键词查询效率高；后者适合常规交易型查询（精确或范围查询）。
2. 倒排索引
   - 通过「词典 + 倒排表」，搜索关键词时只需在内存中快速定位文档列表，效率远高于基于行式扫描或 B+ 树的全文查找。
3. FST（Finite State Transducer）
   - Lucene/ES 将大量的唯一词经过前缀合并与 DAG 压缩，形成紧凑且可快速检索的 FST 字典。
4. 中文+拼音混合检索
   - 在同一个逻辑字段配置多字段（multi-fields），分别采用 IK 分词与 Pinyin 分词进行索引。
   - 查询时可 multi_match 或 bool should 同时匹配中文、拼音字段。
   - 若需要模糊拼音匹配，可使用 nGram，注意索引和性能的平衡。

凭借这些特性，Elasticsearch 能够在海量数据下仍保持高效、高并发的搜索与聚合分析能力。尤其在中文环境中，通过配置多字段与各种分析插件，可以轻松满足“既支持中文分词又兼容拼音搜索”的多元需求。