倒排索引

倒排索引（英语：Inverted index），也常被称为反向索引、置入文件或反向文件，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。

有两种不同的反向索引形式：

后者的形式提供了更多的兼容性（比如短语搜索），但是需要更多的时间和空间来创建。

以英文为例，下面是要被索引的文本：

我们就能得到下面的反向文件索引：

 "a":      {2} "banana": {2} "is":     {0, 1, 2} "it":     {0, 1, 2} "what":   {0, 1}

检索的条件"what", "is" 和 "it" 将对应这个集合：${\displaystyle \{0,1\}\cap <!--\; \cap \; -->\{0,1,2\}\cap <!--\; \cap \; -->\{0,1,2\}=\{0,1\}}$。

对相同的文字，我们得到后面这些完全反向索引，由文档数量和当前查询的单词结果组成的的成对数据。 同样，文档数量和当前查询的单词结果都从零开始。所以，"banana": {(2, 3)} 就是说 "banana"在第三个文档里 (${\displaystyle T_2}$)，而且在第三个文档的位置是第四个单词(地址为 3)。

"a":      {(2, 2)}"banana": {(2, 3)}"is":     {(0, 1), (0, 4), (1, 1), (2, 1)}"it":     {(0, 0), (0, 3), (1, 2), (2, 0)} "what":   {(0, 2), (1, 0)}

如果我们执行短语搜索"what is it" 我们得到这个短语的全部单词各自的结果所在文档为文档0和文档1。但是这个短语检索的连续的条件仅仅在文档1得到。