存储倒排索引

Question

我知道倒排索引是索引单词的好方法，但我困惑的是搜索引擎实际上是如何存储这些单词的？例如，如果一个单词"google“以不同的频率出现在文档- 2、4、6、8中，应该将它们存储在哪里？一个具有一对多关系的数据库表可以用来存储它们吗？

Answer 1

使用成熟的类似SQL的数据库来实现此目的的可能性很小。首先，它被称为反向索引，因为它只是一个索引。每个条目只是一个参考。因为非关系数据库和键值存储成为与web技术相关的热门话题。

• 您只有一种访问数据的方法(通过查询字)。
• 每个条目都是文档引用的列表/数组/向量，所以该列表中的每个元素都非常小。除了存储documentID之外，唯一的其他信息将是存储每个元素的tf-idf分数。

使用方法：

如果您只有一个查询单词("google")，那么您可以在该单词出现的文档的倒排索引中进行查找(在本例中为2、4、6、8)。如果您有tf-idf分数，则可以对结果进行排序，以首先报告最佳匹配的文档。然后查找文档in 2、4、6、8引用的文档，并报告它们的URL以及代码片段等。URL、代码片段等最好存储在另一个表或键值存储中。

如果您有多个查询词("google“和"altavista")，您可以查看这两个查询词的II，得到两个文档If列表(2,4,6,8和3,7,8,11,19)。取两个列表的交集，在本例中为(8)，这是两个查询词都出现的文档列表。

Answer 2

可以肯定的是，每个主要的搜索引擎都有自己的技术来处理倒排索引。它们不是基于标准关系数据库技术，这也是一个比较好的选择。

在谷歌的具体案例中，可以合理地猜测，当前使用的技术是从Fay Chang等人2006年在Bigtable: A Distributed Storage System for Structured Data中描述的BigTable技术派生出来的。不过，毫无疑问，从那时起，这个系统一直在演变。

Answer 3

传统上，倒排索引直接写入文件并存储在磁盘上的某个位置。如果您想执行布尔检索查询(一个文件是否包含查询中的所有单词)，want可能看起来像这样连续存储在文件中。

Term_ID_1:Frequency_N:Doc_ID_1、Doc_ID_2、Doc_ID_N.Term_ID_2:Frequency_N:Doc_ID_1、Doc_ID_2、Doc_ID_N.Term_ID_N:Frequency_N:Doc_ID_1、Doc_ID_2、Doc_ID_N

术语id是术语的id，频率是术语出现的文档数量(换句话说，发布列表有多长)，而文档id是包含术语的文档。

除了索引之外，您还需要知道所有内容在文件中的位置，因此映射也必须存储在另一个文件中的某个位置。例如，给定一个term_id，映射需要返回包含该索引的文件位置，然后可以查找到该位置。由于frequency_id记录在发布中，因此您知道要从文件中读取多少doc_ids。此外，还需要从ID到实际术语/文档名称的映射。

如果你有一个小的用例，你可以通过使用blobs作为发布列表，并在查询时自己处理交叉点，用SQL来实现这一点。

对于非常小的用例，另一个策略是使用术语文档矩阵。