Elasticsearch 使用倒排索引作为其核心数据结构,以实现高效、快速的全文搜索能力。倒排索引是一种索引数据结构,它将文档中的内容映射到包含这些内容的文档列表上。这种方式与传统的关系数据库索引(正向索引)相反,后者是从文档到内容的映射。
倒排索引的基本概念
- Term (词条): 分词后的单个词或短语。
- Term Dictionary (词条字典): 所有词条的集合,通常会使用FST(有限状态转换器)等高效的数据结构来存储,以便快速查找。
- Posting List (倒排列表): 每个词条对应的文档列表,记录了哪些文档包含该词条。
创建倒排索引的过程
- 分词: 将输入的文本(如文档内容)分割成多个词条。这个过程可能包括去除停用词(如“的”、“和”等常见但无实际意义的词)、词形还原(如将“running”还原为“run”)等步骤。
- 构建词条字典: 将所有词条收集起来,构建一个词条字典,确保每个词条都能快速定位。
- 构建倒排列表: 对于每个词条,记录下所有包含该词条的文档ID,形成倒排列表。
查询倒排索引的过程
- 解析查询: 对用户输入的查询进行分词,得到查询词条。
- 查找倒排列表: 根据查询词条,在词条字典中找到对应的倒排列表。
- 合并结果: 如果查询包含多个词条,则需要合并各个词条对应的倒排列表,找出共同出现的文档。
- 评分排序: 根据文档的相关性对结果进行评分,并按评分排序返回给用户。
特殊结构 - Doc Values
除了倒排索引外,Elasticsearch 还使用了 doc values
结构来优化排序和聚合操作。doc values
可以视为倒排索引的转置,即为每个字段创建一个从文档ID到字段值的映射,允许在不加载整个文档的情况下执行排序和聚合操作,从而提高性能。
总结
倒排索引是 Elasticsearch 实现高效搜索的关键技术之一。通过预先处理文档内容,构建词条字典和倒排列表,Elasticsearch 能够在海量数据中快速定位相关文档,满足实时搜索的需求。同时,通过诸如 doc values
等特殊结构的引入,Elasticsearch 还能有效支持排序和聚合等高级功能。