一、倒排索引基础概念

倒排索引是 Elasticsearch 实现高效全文搜索的核心技术。它通过将词项与文档 ID 关联，支持快速检索、短语查询、布尔查询和相关性评分。尽管倒排索引在存储和更新方面有一定的开销，但通过词典优化、倒排列表压缩、分片和缓存等技术，Elasticsearch 能够高效地处理大规模数据的搜索需求。

二、倒排索引基本结构

倒排索引的核心是：词典（Term Dictionary） 和 倒排列表（Posting List）。

1. 词典（Term Dictionary）：
   • 作用：存储所有文档中出现的词项（Terms），并按字典序排序。
   • 特点：
     • 支持快速查找某个词项是否存在。
     • 存储词项的元数据，如文档频率（Document Frequency, DF）。
   • 数据结构：
     • 通常使用 FST（Finite State Transducer） 存储，支持高效的前缀查找和范围查询。
2. 倒排列表（Posting List）：
   • 作用：记录包含某个词项的所有文档及其相关信息。
   • 内容：
     • 文档 ID（DocID）：标识包含该词项的文档。
     • 词频（Term Frequency, TF）：词项在文档中出现的次数。
     • 位置信息（Positions）：词项在文档中的具体位置（用于短语查询或高亮显示）。
     • 偏移量（Offsets）：词项在文档中的起始和结束位置（可选）。
   • 存储优化：
     • 使用 差值编码（Delta Encoding） 压缩文档 ID 和位置信息。
     • 使用 FOR（Frame of Reference） 或 RLE（Run-Length Encoding） 等压缩算法减少存储空间。

示例：

• 文档内容

  • 文档 1：“Elasticsearch is powerful”
  • 文档 2：“Elasticsearch is fast and powerful”

• 分词结果
  经过分词和标准化处理后，生成的词项（Terms）如下：

  • 文档 1 的词项：[“elasticsearch”, “is”, “powerful”]
  • 文档 2 的词项：[“elasticsearch”, “is”, “fast”, “and”, “powerful”]

• 倒排索引结构

  1. 词项字典（Term Dictionary）
     词项字典存储所有词项及其元数据（如文档频率）：

     词项（Term）	文档频率（DF）
     “and”	1
     “elasticsearch”	2
     “fast”	1
     “is”	2
     “powerful”	2

  2. 倒排列表（Posting List）
     每个词项对应一个倒排列表，记录包含该词项的文档及其相关信息（如文档 ID、词频、位置信息、偏移量等）。

     • 词项 “elasticsearch”

       文档 ID（DocID）	词频（TF）	位置信息（Positions）	偏移量（Offsets）
       1	1	[0]	[(0, 13)]
       2	1	[0]	[(0, 13)]

     • 词项 “is”

       文档 ID（DocID）	词频（TF）	位置信息（Positions）	偏移量（Offsets）
       1	1	[1]	[(14, 16)]
       2	1	[1]	[(14, 16)]

     • 词项 “powerful”

       文档 ID（DocID）	词频（TF）	位置信息（Positions）	偏移量（Offsets）
       1	1	[2]	[(17, 25)]
       2	1	[4]	[(27, 35)]

     • 词项 “fast”

       文档 ID（DocID）	词频（TF）	位置信息（Positions）	偏移量（Offsets）
       2	1	[2]	[(17, 21)]

     • 词项 “and”

       文档 ID（DocID）	词频（TF）	位置信息（Positions）	偏移量（Offsets）
       2	1	[3]	[(22, 25)]

  3. 压缩与存储优化
     在实际存储中，Elasticsearch 会对倒排列表进行压缩和优化：

     • 文档 ID：使用差值编码（Delta Encoding）压缩。例如，文档 ID [1, 2] 存储为 [1, 1]（差值）。
     • 位置信息：使用差值编码压缩。例如，位置信息 [0, 1, 2] 存储为 [0, 1, 1]（差值）。
     • 偏移量：使用差值编码压缩。

  4. 完整倒排索引结构

     {
       "terms": {
         "and": {
           "doc_freq": 1,
           "postings": [
             {
               "doc_id": 2,
               "term_freq": 1,
               "positions": [3],
               "offsets": [(22, 25)]
             }
           ]
         },
         "elasticsearch": {
           "doc_freq": 2,
           "postings": [
             {
               "doc_id": 1,
               "term_freq": 1,
               "positions": [0],
               "offsets": [(0, 13)]
             },
             {
               "doc_id": 2,
               "term_freq": 1,
               "positions": [0],
               "offsets": [(0, 13)]
             }
          ]
         },
         "fast": {
           "doc_freq": 1,
           "postings": [
             {
               "doc_id": 2,
               "term_freq": 1,
               "positions": [2],
               "offsets": [(17, 21)]
             }
           ]
         },
         "is": {
           "doc_freq": 2,
           "postings": [
             {
               "doc_id": 1,
               "term_freq": 1,
               "positions": [1],
               "offsets": [(14, 16)]
             },
             {
               "doc_id": 2,
               "term_freq": 1,
               "positions": [1],
               "offsets": [(14, 16)]
             }
           ]
         },
         "powerful": {
           "doc_freq": 2,
           "postings": [
             {
               "doc_id": 1,
               "term_freq": 1,
               "positions": [2],
               "offsets": [(17, 25)]
             },
             {
               "doc_id": 2,
               "term_freq": 1,
               "positions": [4],
               "offsets": [(27, 35)]
             }
           ]
         }
       }
     }
     

三、倒排索引的构建过程

Elasticsearch 的倒排索引构建过程是其高效搜索能力的核心。以下是倒排索引构建的详细步骤：

1. 文档接收与预处理：
   当文档被写入 Elasticsearch 时，首先会经过预处理：

   • 字段解析：根据字段类型（text、keyword、date 等）决定处理方式。
   • 动态映射：若字段未预先定义映射，Elasticsearch 会自动推断类型（如文本字段默认设为 text 并添加 keyword 子字段）。

2. 文本分析与分词：
   针对 text 类型字段，执行文本分析（Text Analysis）：

   • 对文档中的文本字段进行分析，生成标准化的词项（Terms）。
   • 分析过程包括以下步骤：
     1. 字符过滤：移除 HTML 标签、特殊符号等（如使用 html_strip 过滤器）。
     2. 分词（Tokenization）：通过分词器（如 standard 分词器）将文本拆分为词项（Tokens）。
     3. 词项处理：
        • 小写转换（Lowercasing）：“Elasticsearch” → “elasticsearch”。
        • 去除停用词（Stop Words）：移除 “is”、“the” 等无实际意义的词。
        • 词干提取（Stemming）：“running” → “run”（如使用 porter_stem 过滤器）。
        • 同义词扩展（Synonyms）：“quick” → [“quick”, “fast”]。

3. 构建倒排索引：
   Lucene（Elasticsearch 的底层引擎）将数据组织为 倒排列表（Postings List） 和 词典（Term Dictionary）：

   • 倒排列表（Posting List）：
     为每个词项创建一个倒排列表，包含以下信息：
     • 文档 ID：标识包含该词项的文档。
     • 词频（Term Frequency）：词项在文档中出现的次数。
     • 位置信息（Positions）：词项在文档中的具体位置（用于短语查询或高亮显示）。
     • 偏移量（Offsets）：词项在文档中的起始和结束位置（可选）。
   • 词典（Term Dictionary）：
     所有词项的排序列表，使用 FST（Finite State Transducer） 压缩存储，支持快速查找：
     • 将所有词项按字典序排序。
     • 通过跳表（Skip List）加速范围查询。

4. 索引段（Segment）的生成
   Lucene 通过分段机制提升写入性能：

   • 写入流程：
     1. 新文档写入内存缓冲区，生成新段（Segment），每个段包含一个完整的倒排索引，以及词典、倒排列表等信息。。
     2. 通过 Refresh 操作（默认 1 秒）将段写入文件系统缓存，开放查询。
     3. 通过 Flush 操作（默认 30 分钟）将文件系统缓存数据持久化到磁盘。

5. 段的合并（Segment Merging）

   • 随着文档的不断写入，段的数量会逐渐增加，影响查询性能。
   • Elasticsearch 会定期执行段合并，合并策略有如下：
     1. 分层合并（Tiered Merge Policy）：默认策略，优先合并大小相近的段。
     2. 逻辑合并（Log Merge Policy）：适用于时间序列数据。

6. 倒排索引存储与压缩
   倒排索引以高效的文件格式存储，并使用压缩技术减少存储空间。

   • 存储与压缩包括以下内容：
     1. 词典存储：
        • 使用 FST（Finite State Transducer）等数据结构存储词典，支持快速查找。
     2. 倒排列表存储：
        • 使用 FOR（Frame of Reference）、RLE（Run-Length Encoding）等压缩算法存储倒排列表。
     3. 位置信息存储：
        • 使用差值编码（Delta Encoding）等技术压缩位置信息。

7. 分布式环境下的索引构建
   Elasticsearch 是分布式系统，索引构建过程涉及分片和副本：

   1. 分片（Sharding）：
      • 索引被分成多个分片，分布在不同节点上，每个分片是一个独立的倒排索引。
   2. 副本（Replication）：
      • 每个分片可以有多个副本，提高可用性和查询性能。
   3. 分布式写入：
      • 文档写入时，会根据路由规则（如 _id 哈希）分配到对应的分片。
   4. 一致性保证：
      • Elasticsearch 使用主从复制机制，确保数据一致性。

四、倒排索引的优势

倒排索引的主要优势在于：

1. 高效的全文搜索：
   • 快速定位文档：通过词项（Term）快速找到包含该词项的所有文档。
   • 支持布尔查询：支持 AND、OR、NOT 等逻辑操作，便于构建复杂的查询条件。
   • 示例：
     • 在下面这个例子中，Elasticsearch 会从倒排索引中查找 “fast” 对应的文档 ID 列表，并返回相关文档。

     GET /my_index/_search
     {
       "query": {
         "match": {
           "content": "fast"
         }
       }
     }
     

2. 支持短语查询：
   • 精确匹配短语：可以查找包含特定短语的文档。
   • 支持位置查询：支持基于词项位置的查询（如邻近查询）。
   • 示例：
     • 在下面这个例子中，Elasticsearch 会查找 “is” 和 “fast” 在文档中相邻的位置，并返回匹配的文档。

     GET /my_index/_search
     {
       "query": {
         "match_phrase": {
           "content": "is fast"
         }
       }
     }
     

3. 支持相关性评分：
   • TF-IDF 评分：基于词频和文档频率计算文档的相关性。
   • BM25 评分：更先进的评分算法，适用于现代搜索引擎。
   • 示例：
     • 在下面这个例子中，Elasticsearch 会计算每个文档的相关性评分，并返回最相关的文档。

     GET /my_index/_search
     {
       "query": {
         "match": {
           "content": "elasticsearch"
         }
       }
     }
     

4. 支持多字段搜索
   • 跨字段查询：可以在多个字段中搜索同一个词项。
   • 字段优先级：可以为不同字段设置不同的权重，影响相关性评分。
   • 示例：
     • 在下面这个例子中，Elasticsearch 会在 title 和 content 字段中搜索 “fast”，并返回匹配的文档。

     GET /my_index/_search
     {
       "query": {
         "multi_match": {
           "query": "fast",
           "fields": ["title", "content"]
         }
       }
     }
     

5. 高效的布尔查询
   • AND 查询：查找同时包含多个词项的文档。
   • OR 查询：查找包含任意一个词项的文档。
   • NOT 查询：排除包含特定词项的文档。
   • 示例：
     • 在下面这个例子中，Elasticsearch 会查找同时包含 “fast” 和 “powerful” 的文档。

     GET /my_index/_search
     {
       "query": {
         "bool": {
           "must": [
             { "match": { "content": "fast" } },
             { "match": { "content": "powerful" } }
           ]
         }
       }
     }
     

6. 支持前缀和通配符查询
   • 前缀查询：查找以特定前缀开头的词项。
   • 通配符查询：查找符合特定模式的词项。
   • 示例：
     • 在下面这个例子中，Elasticsearch 会查找以 “elast” 开头的词项（如 “elasticsearch”）。

     GET /my_index/_search
     {
       "query": {
         "wildcard": {
           "content": "elast*"
         }
       }
     }
     

7. 支持模糊查询
   • 容错搜索：支持查找与目标词项相似的词项。
   • 编辑距离：可以指定允许的最大编辑距离。
   • 示例：
     • 在下面这个例子中，Elasticsearch 会查找与 “elastik” 相似的词项（如 “elasticsearch”）。

     GET /my_index/_search
     {
       "query": {
         "fuzzy": {
           "content": "elastik"
         }
       }
     }
     

8. 高效的压缩存储
   • 差值编码（Delta Encoding）：对有序的文档 ID 列表进行压缩。
   • FOR（Frame of Reference）：对数值型文档 ID 列表进行压缩。
   • RBM（Roaring Bitmaps）：对稀疏文档 ID 列表进行压缩。
9. 支持动态更新
   • 实时搜索：新文档可以快速被索引并支持搜索。
   • 增量更新：只更新受影响的倒排列表，减少更新开销。

五、倒排索引的局限性

尽管倒排索引非常强大，但它也有一些局限性：

1. 存储开销：
   • 词项存储：倒排索引需要存储所有文档中的词项及其对应的文档列表，词项数量庞大时，存储开销较大。
   • 位置信息：为支持短语查询，还需存储词项在文档中的位置信息，进一步增加存储需求。
2. 更新开销：
   • 实时性差：倒排索引的更新需要重建部分索引，频繁更新会影响性能。
   • 删除操作复杂：删除文档时，标记删除而非立即移除，可能导致索引膨胀，需定期合并段（segment merging）来清理。
3. 查询性能
   • 长尾词项：某些词项出现在大量文档中，查询这些词项时性能较差。
   • 复杂查询：布尔查询、短语查询等复杂操作需要合并多个词项的倒排列表，计算量大，性能下降。
4. 内存消耗
   • 缓存需求：为提升查询性能，常将部分倒排索引缓存到内存，词项多时内存消耗大。
   • 堆内存压力：Elasticsearch 依赖 JVM 堆内存，大规模数据时可能引发 GC 问题，影响性能。
5. 不适合数值范围查询：
   • 倒排索引主要用于文本搜索，对于数值范围查询（如 age > 30），Elasticsearch 使用 BKD Tree 等其他数据结构。
6. 文本分析的局限性
   • 分词依赖：倒排索引依赖分词器，分词效果直接影响查询准确性，不同语言和领域的分词效果可能不理想。
   • 同义词与语义理解：难以处理同义词和语义理解，需额外配置同义词词典或使用 NLP 技术。

六、倒排索引的用途

倒排索引主要用于以下场景：

1. 全文搜索
   • 支持对文本字段的高效全文搜索，通过词项（Term）快速定位包含该词项的文档。
   • 例如，搜索 “fast” 时，Elasticsearch 会查找倒排索引中 “fast” 对应的文档 ID 列表。
2. 短语查询
   • 支持搜索包含特定短语的文档，倒排索引中存储了词项的位置信息（Positions），可以精确匹配短语中词项的顺序和位置。
   • 例如，搜索 “Elasticsearch is” 时，可以找到文档中连续出现这两个词项的位置。
3. 近似查询
   • 支持搜索词项之间距离在一定范围内的文档，利用倒排索引中的位置信息，计算词项之间的距离。
   • 例如，搜索 “Elasticsearch” 和 “powerful” 之间距离不超过 5 个词的文档。
4. 高亮显示
   • 在搜索结果中高亮显示匹配的词项，倒排索引中存储了词项的偏移量（Offsets），可以精确定位词项在文档中的起始和结束位置。
   • 根据偏移量提取匹配的词项并进行高亮显示。
5. 相关性评分
   • 根据文档与查询的相关性对搜索结果进行排序，倒排索引中存储了词频（Term Frequency, TF）和文档频率（Document Frequency, DF）。
   • 使用 TF-IDF 或 BM25 等算法计算文档的相关性评分。
   • 评分越高，文档与查询的相关性越强。
6. 聚合分析
   • 支持对搜索结果进行统计分析，倒排索引中存储了词项的文档频率（DF），可以快速计算词项的全局统计信息。
   • 例如，计算某个词项在所有文档中出现的频率。
7. 自动补全
   • 支持搜索时的自动补全功能，倒排索引的词典（Term Dictionary）支持前缀查找，可以快速匹配用户输入的部分词项。
   • 例如，输入 “elas” 时，可以自动补全为 “Elasticsearch”。
8. 过滤
   • 支持对搜索结果进行过滤，倒排索引可以快速判断某个词项是否存在于文档中。
   • 例如，过滤出包含 “powerful” 但不包含 “slow” 的文档。
9. 排序
   • 支持对搜索结果按指定字段排序，倒排索引可以快速访问文档的元数据（如文档 ID、词频等），用于排序。
   • 例如，按文档的创建时间或评分进行排序。

七、倒排索引的优化

Elasticsearch 在倒排索引的设计和实现中进行了多种优化，以提高存储效率、查询性能和扩展性。以下是 Elasticsearch 对倒排索引的主要优化措施：

1. 压缩技术

   • 目的：减少存储空间，提高内存和磁盘的利用率。
   • 具体优化：
     • 文档 ID 压缩：使用 差值编码（Delta Encoding） 对文档 ID 进行压缩。
     • 位置信息压缩：使用差值编码对词项的位置信息进行压缩。
     • 倒排列表压缩：使用 FOR（Frame of Reference） 和 RLE（Run-Length Encoding） 等算法压缩倒排列表。
     • 词典压缩：使用 FST（Finite State Transducer） 压缩词典，支持高效的前缀查找和范围查询。

2. 索引段（Segment）管理

   • 目的：提高写入性能和查询效率。
   • 具体优化：
     • 分段存储：索引由多个不可变的段（Segment）组成，每个段是一个独立的倒排索引。
     • 近实时刷新：新写入的文档会先在内存中构建倒排索引，然后定期刷新到磁盘生成新的段。
     • 段合并：定期将多个小段合并为更大的段，减少段的数量，提升查询性能。
     • 删除文档清理：在段合并过程中，标记为删除的文档会被物理删除，释放存储空间。

3. 缓存机制

   • 目的：加速查询性能。
   • 具体优化：
     • 过滤器缓存（Filter Cache）：缓存常用的过滤查询结果，减少重复计算。
     • 字段数据缓存（Field Data Cache）：缓存字段的倒排索引数据，加速聚合和排序操作。
     • 查询结果缓存（Query Cache）：缓存查询结果，适用于重复查询。
     • 分片查询缓存（Shard Query Cache）：缓存分片级别的查询结果。

4. 分布式架构

   • 目的：支持大规模数据和高并发查询。
   • 具体优化：
     • 分片（Sharding）：将索引分成多个分片，分布在不同节点上，每个分片是一个独立的倒排索引。
     • 副本（Replication）：每个分片可以有多个副本，提高可用性和查询性能。
     • 分布式查询：查询时，协调节点将请求分发到相关分片，合并结果后返回给客户端。

5. 高效的查询执行

   • 目的：加速复杂查询的执行。
   • 具体优化：
     • 跳过不匹配的文档：利用倒排列表的压缩和分块存储，快速跳过不匹配的文档。
     • 布尔查询优化：对布尔查询（AND、OR、NOT）进行优化，减少不必要的计算。
     • 短语查询优化：利用位置信息快速匹配短语。

6. 近实时搜索

   • 目的：支持近实时的数据搜索。
   • 具体优化：
     • 内存索引：新写入的文档会先在内存中构建倒排索引。
     • 定期刷新：每隔一段时间（默认 1 秒），内存中的索引会被刷新到磁盘，生成新的段。
     • 可搜索性：刷新后，新文档可以立即被搜索到。

7. 动态更新与删除

   • 目的：支持高效的文档更新和删除。
   • 具体优化：
     • 标记删除：删除文档时，不会立即从倒排索引中移除，而是标记为删除。
     • 段合并清理：在段合并过程中，标记为删除的文档会被物理删除。
     • 更新操作：更新文档时，会生成新版本的文档，旧版本的文档会被标记为删除。

8. 字段数据类型的优化

   • 目的：针对不同数据类型优化存储和查询。
   • 具体优化：
     • 文本字段：使用倒排索引支持全文搜索。
     • 数值字段：使用 BKD Tree 等数据结构支持范围查询和排序。
     • 地理位置字段：使用 GeoHash 或 Quadtree 支持地理位置查询。

八、倒排索引 和 正排索引的区别

在 Elasticsearch 中，倒排索引（Inverted Index） 和 正排索引（Forward Index） 是两种不同的数据结构，分别用于支持不同的搜索和检索功能。以下是它们的核心区别：

1. 定义与用途

   特性	倒排索引（Inverted Index）	正排索引（Forward Index）
   定义	存储词项到文档的映射关系，用于快速定位包含某个词项的文档。	存储文档到字段值的映射关系，用于快速返回文档的原始内容。
   主要用途	支持全文搜索、短语查询、模糊查询等。	支持字段检索、聚合分析、排序、脚本计算等。

2. 数据结构

   特性	倒排索引（Inverted Index）	正排索引（Forward Index）
   存储方式	词项到文档的映射（Term → Document）。	文档到字段值的映射（Document → Field Values）。
   核心组成部分	-词典（Term Dictionary） -倒排列表（Posting List）	- 文档 ID（DocID） - 字段值（Field Values）

3. 存储内容

   特性	倒排索引（Inverted Index）	正排索引（Forward Index）
   存储内容	- 词项（Term） - 文档 ID（DocID） - 词频（TF） - 位置信息（Positions） - 偏移量（Offsets）	- 文档 ID（DocID） - 字段值（Field Values）

4. 查询方式

   特性	倒排索引（Inverted Index）	正排索引（Forward Index）
   查询方式	通过词项查找包含该词项的文档。	通过文档 ID 查找文档的字段值。

5. 适用场景

   特性	倒排索引（Inverted Index）	正排索引（Forward Index）
   适用场景	- 全文搜索 - 短语查询 - 模糊查询 - 高亮显示	- 字段检索 - 聚合分析 - 排序 - 脚本计算

6. 性能优化

   特性	倒排索引（Inverted Index）	正排索引（Forward Index）
   优化技术	- 压缩技术（如 FST、FOR、RLE） - 缓存机制 - 段合并	- Doc Values 列式存储 - 字段数据缓存 - 压缩技术