Elasticsearch-倒排索引

Elasticsearch和Lucene的关系

    Lucene 是一个开源、免费、高性能、纯 Java 编写的全文检索引擎，可以算作是开源领域最好的全文检索工具包。ElasticSearch 是基于Lucene实现的一个分布式、可扩展、近实时性的高性能搜索与数据分析引擎。

Lucene索引层次结构

Lucene的基础层次结构由索引、段、文档、域、词五个部分组成。正向索引的生成即为基于Lucene的基础层次结构一级一级处理文档并分解域存储词的过程。

索引文件层级关系如图1所示：

• 索引（Index）：Lucene索引库包含了搜索文本的所有内容，可以通过文件或文件流的方式存储在不同的数据库或文件目录下。

• 段（Segment）：一个索引中包含多个段，段与段之间相互独立。由于Lucene进行关键词检索时需要加载索引段进行下一步搜索，如果索引段较多会增加较大的I/O开销，减慢检索速度，因此写入时会通过段合并策略对不同的段进行合并。

• 文档（Document）：Lucene会将文档写入段中，一个段中包含多个文档。

• 域（Field）：一篇文档会包含多种不同的字段，不同的字段保存在不同的域中。

• 词（Term）：Lucene会通过分词器将域中的字符串通过词法分析和语言处理后拆分成词，Lucene通过这些关键词进行全文检索。

倒排索引

其中主要有如下几个核心术语需要理解：

• 词条（Term）： 索引里面最小的存储和查询单元，对于英文来说是一个单词，对于中文来说一般指分词后的一个词。

• 词典（Term Dictionary）： 或字典，是词条 Term 的集合。搜索引擎的通常索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。

• 倒排表（Post list）： 一个文档通常由多个词组成，倒排表记录的是某个词在哪些文档里出现过以及出现的位置。每条记录称为一个倒排项（Posting）。倒排表记录的不单是文档编号，还存储了词频等信息。

• 倒排文件（Inverted File）： 所有单词的倒排列表往往顺序地存储在磁盘的某个文件里，这个文件被称之为倒排文件，倒排文件是存储倒排索引的物理文件。

• 字典树（Term Index）： 从数据结构上分类算是一个“Trie 树”，也就是我们常说的字典树。这棵树不会包含所有的 term，它包含的是 term 的一些前缀（这也是字典树的使用场景，公共前缀）。通过 term index 可以快速地定位到 term dictionary 的某个 offset。

索引查询及文档搜索过程

Lucene利用倒排索引定位需要查询的文档号，通过文档号搜索出文件后，再利用词权重等信息对文档排序后返回。

• 内存加载tip文件，根据FST匹配到后缀词块在tim文件中的位置；

• 根据查询到的后缀词块位置查询到后缀及倒排表的相关信息；

• 根据tim中查询到的倒排表信息从doc文件中定位出文档号及词频信息，完成搜索；

• 文件定位完成后Lucene将去.fdx文件目录索引及.fdt中根据正向索引查找出目标文件。

文件格式如图4所示：

索引算法