我的灵感记录
文章 标签 分类 友链 树洞 片段
我的灵感记录

目录

目录

ES数据模型之倒排索引

 收录于  类别 技术
     约 2477 字   预计阅读 11 分钟    次阅读     条评论  

问题：怎么在多个长文本中查询包含某个 关键词 的哪个 ？

常规方法需要依次遍历多个长文本，判断每一个长文本中是否含有该关键词，该方法效率比较低。

与此同时，此类问题非常常见，如搜索引擎、购物网站的关键字搜索。

那么我们该怎么来优化此问题呢。

我们可以使用 倒排索引 。

  1. 首先我们对长文本进行分词（英文使用空格就可以，中文挺复杂的），分词后我们得到词项（term）。
  2. 记录词项和文本 id 之间的对应关系，比如单词 hello 对应的文本id为 1,3,30。

需要查询时就可以依次遍历词项即可找到对应的长文本 id。此时的时间复杂度为 O(N) 。

我们可以继续优化，将词项按照字典顺序排序，那么在查询是即可使用二分查找，此时的时间复杂度为O(lgN)。

其中已经按照字典排序的词项被称为 Term dictionary ，对应的长文本 id 列表被称为 Postings list。整个这个用于优化搜索的结构被称为 倒排索引（Inverted Index） 。

因为有很多词项 ，所以 Term dictionary 会很大，那么将其放在内存中是不合适的，需要放在磁盘中，读取磁盘进行搜索，速度远远低于读取内存进行搜索，那么有优化手段吗？

有的，我们可以在内存中构建一个 前缀树，因为很多词项与词项之前的前缀是相同的，我们可以使用这些前缀精简一个前缀树，在叶子节点存储该词项在 Term dictionary 的偏移量（或指针）。根据此偏移量可以快速定义磁盘上的 Postings list。这个树结构体积小，适合常驻内存，即所谓的 Term Index。

截止目前，通过 Term Index 加速搜索，我们可以快速定位到 Postings list，但是 Postings list 中存储的是长文本 id，我们需要一个地方来存储实际的完整的长文本内容，这就是 Stored Fields，一个行式存储结构。

有时，我们需要根据某个字段对文档进行排序，比如按照日志发生时间排序。 我们就需要先从每一条行式存储结构的数据中提取时间（即从 Stored Fields 中），然后再进行排序，并不高效。那么有没有更好的方法呢？

可以采用空间换时间的思路。提前将散落在各个文档的字段进行集中存放，并且保留文档到字段的正向映射关系。需要排序时，只需将该字段读取出来进行排序即可。这种列式存储结构，就是 Doc Values。其默认存储在磁盘上，但是会被缓存到内存上以提高性能。除了排序，其还被用于聚合、脚本中访问字段值以及某些查询（如 term）等。

以上介绍了 4 种数据结构，Inverted Index、Term Index、Stored Fields 和 Doc Values，它们合在一起构成了一个独立的、功能完整的索引单元，即 Segment。它包含文档数据、倒排索引结构和其他元数据，物理上表现为一组文件（.cfs , .si, .doc 等）。它具有不可变性，一旦创建不可修改（只能读取或整个删除），更新操作其实被转换成了追加新的版本，然后后台线程定期压缩合并删除这些 Segment。

为什么要这么设计呢，不更新，只追加？

  1. 因为 Segment 是存储在磁盘上的，写入速度远低于内存，追加和分段合并都属于顺序写入操作，通常快于随机写入。
  2. Segment 文件一旦创建不可变的特性，使并发操作和崩溃恢复都更简单了。
  3. 合并旧的 Segment 可以避免数据文件随时间推移而分散。

这些多个 Segment 就共同构成一个单机文件检索库，即著名的开源基础搜索库 Lucene。

实际上面所说的是简化的模型，在实际 ES 中，Term index 使用一种更高效的数据结构——FST(Finite State Transducer , 有限状态转换器)来加速词项的查询。

FST类似与压缩的前缀树，但是更节约内存，它不仅会合并相同的前缀，还会合并相同的后缀，所以相比前缀树更加紧凑。其本质是 确定性无环状态机。另外，相比传统前缀树，FST不仅存储词项，还能关联值。

Elasticsearch 的倒排索引分为两部分：

  1. Term Index（内存中）：

    • 使用 FST 实现，用于快速定位词项。
    • 叶子节点存储指向 Term Dictionary 的偏移量（如文件指针）。

  2. Term Dictionary + Postings List（磁盘中）：

    • Term Dictionary：有序的词项列表，存储词项及其元数据（如 doc_freq、postings_offset）。
    • Postings List：存储包含该词项的文档ID列表（如 DocId）、词频（TF）、位置信息等。

Elasticsearch的数据查询过程，假设搜索词项 "apple"：

  1. 内存中查询 Term Index（FST）：

    • 遍历 FST 的路径 a → p → p → l → e，到达叶子节点。
    • 获取叶子节点存储的 偏移量 offset=1000（指向磁盘中的 Term Dictionary）。

  2. 磁盘中读取 Term Dictionary：

    • 根据偏移量 1000，找到 "apple" 在 Term Dictionary 中的条目，获取元数据：
      {
  "term": "apple",
  "doc_freq": 5,          // 出现该词项的文档数
  "postings_offset": 2000 // 指向倒排列表的指针
}

  3. 加载 Postings List：

    • 根据 postings_offset=2000，从磁盘读取倒排列表：
      {
  "doc_ids": [1, 3, 7],  // 包含"apple"的文档ID
  "tfs": [2, 1, 4],       // 各文档中的词频
  "positions": [...]      // 词项在文档中的位置
}

在 Elasticsearch 中，每个 Segment 确实包含完整的索引数据结构，主要包括以下组件：

  1. 倒排索引 (Inverted Index)

    • .tip 和 .tim 文件：存储术语字典和倒排列表
    • 实现从词项(term)到文档的快速映射
    • 支持全文搜索的核心数据结构

  2. 词项索引 (Term Index)

    • .tip 文件：作为术语字典的索引
    • 使用 FST (Finite State Transducer) 数据结构实现
    • 加速术语查找过程

  3. 存储字段 (Stored Fields)

    • .fdt 和 .fdm 文件
    • 存储原始文档的完整内容
    • 用于返回 _source 字段或显式指定 store: true 的字段

  4. 文档值 (Doc Values)

    • .dvd 和 .dvm 文件
    • 列式存储结构，用于排序、聚合和脚本操作
    • 默认对所有非 text 字段启用

  5. 正向索引 (Postings List)

    • .doc 文件：存储文档ID和词频信息
    • 支持短语查询和位置感知查询

  6. 删除文档标记

    • .liv 文件：标记哪些文档已被删除
    • 逻辑删除，物理删除发生在段合并时

  7. 列存字段 (对于时序数据特别重要)

    • 在较新版本中引入的更高效的列式存储

Segment 的创建过程如下：

  • 新文档首先写入内存缓冲区（In-memory Buffer）；
  • 达到阈值后刷新（flush）到磁盘形成新的 Segment ，可以保证持久化；
  • 每次 refresh 操作都会生成一个 Segment，此时可以立即被搜索，但是数据只是到文件系统缓存，不能保证持久化。默认 refresh_interval=1s，所以 ES 比传统数据库稍慢，但是比完全刷盘快，是提供**近实时搜索（NRT）**的关键。

Segment 的合并过程如下：

  • 后台线程定期通过 Merge Policy 控制小 Segment 合并为大 Segment；
  • 合并时删除标记为删除的文档，合并重复文档（保留最新版本），优化索引结构；
  • 减少 Segment 数量提高查询效率。
更新于 2025-06-14
 Es, 倒排索引
 | 主页