倒排索引和普通索引有什么区别？

Question

倒排索引和普通索引有什么区别？

indexingterminology

123

在软件工程中，我们经常创建索引（例如在数据库中），但我也经常听到很多人谈论倒排索引。它们两者之间有什么根本性的不同吗？它们听起来像是一回事。

在软件工程中，我们经常创建索引（例如在数据库中），但是我也听到很多人谈论倒排索引。它们两者之间是否有根本的不同呢？它们听起来好像是一样的东西。

- guidoism

3

http://en.wikipedia.org/wiki/Inverted_index - paxdiablo

澄清一下，您的问题是：普通索引（http://en.wikipedia.org/wiki/Index_%28database%29）与根据已存在于该表中的数据拆分表格的索引有何不同？是这样吗？ - jwheron

4

@guidoism大家没有提到的一点是（normalocity通过例子部分描述了它，lovesh几乎说得很准），倒排索引将基础数据"反转"以提高效率（例如交换键/数据以从不同角度进行搜索或按字母/数字顺序排序以允许快速搜索算法），而标准索引会按照发现的数据存储。 "反向/正向"引用和单词"invert"的字面含义在这里不适用，相反，它指的是将数据反转以生成特定于手头任务的有效格式。 - TheManWithNoName

8个回答

38

他们之所以称为倒排索引，是因为已经存在正向索引。以搜索引擎为例，它由两部分组成：第一部分是“网络爬虫和解析器”，它从文档到单词构建索引；第二部分是搜索数据库，它从单词到文档构建索引。因为第一个索引已经存在，我们自然将第二个索引称为倒排索引。

如果你将书的目录（Table of Content）命名为索引，则应该将书末的索引称为“倒排索引”。或者，从另一方面来说，你可以将目录称为倒排索引。

- xeranic

10

这应该是被认可的答案，因为它回答了一个问题：即使它只是大家所认为的“正常索引”，为什么我们称索引为“倒排”索引。在SQL b-tree索引中，为每个单词存储一个指针以指向包含它的所有行（“文档”）。在那里我们称其为“索引”。但在搜索引擎中，我们突然将这个完全相同的过程称为“倒排索引”。不是因为它本质上有区别，而是因为我们先创建了一个“向前索引”（分割文本），然后再将其“反转”。因此，总体而言，“反转”这个名称来自于创建它的过程，而不是它最终的索引结构。 - Foo Bar

@xeranic 感谢您的见解。快速问题：在反向索引构建完成后，从正向索引文件中删除条目是否实用？ - Roy Lee

3

我同意@FooBar的观点，这个答案应该被选为正确答案。它解释了为什么尽管我们生活中所有的正常索引都被归类为“反向”，但我们仍然需要发明一个新术语“倒排索引”。 - Ryan Lyu

8

< p > normalocity已经很好地区分了正向索引和倒排索引，但是关于为什么一个被称为正向索引，另一个被称为倒排索引，也许这就是它们被称为这样的原因——

以搜索引擎抓取和索引（或为书建立索引）为例，可以在爬行网页（或阅读书籍）时同时构建正向索引，或者说向前。因此，如果您有10个要爬取的网页（或10个章节），您可以爬取第一个网页（阅读第一章），然后列出出现在该网页中的单词列表（出现在该章中的单词），并继续进行其他网页（其他章节）的操作，因此当您爬取所有10个网页（阅读所有10个章节）时，您的正向索引已经完成，每个网页（章节）都指向包含的单词列表。

但是，要创建倒排索引，您必须爬取所有10个网页（阅读10个章节），然后从每个文档列表中获取每个单词，并确定哪些文档包含该单词。因此，这就像在爬行网页（阅读书籍章节）后向后移动。因此它被称为倒排索引。

这只是我的猜测。

- lovesh

8

术语“倒排索引”指的是将包含许多单词的单个文档与每个唯一单词（或标识）包含（或标识）许多文档的列表相对应。这实际上是将一个一对多关系（文档到单词）倒置（或反转），使得现在存在一个新的“倒置”的一对多关系，即每个唯一单词与许多文档相关联（即包含该单词的所有文档）。它的起源真的很简单，术语“倒排索引”早在计算机和电子高速索引之前就用来描述同类型的手动索引（是的，我承认我是一名年迈的程序员，几乎已经到了可以认为格雷斯·霍珀是适合约会的“甜美少女”的年龄）。请不要轻易抛弃我们这些老古董，因为我们可能会偶尔提供一两个有用的，甚至有价值的历史小知识 - 前提是我们的个人RAM仍然正常工作。[微笑]

- user1009

8

通常说到索引时，指的是为了加速应用程序（例如MySQL或其他关系型数据库请查阅MySQL文档）而进行的一些计算或存储结果。索引也可能与缓存等有关。

反向索引创建具有主要用于（全文）搜索的结构的文件。

反向索引由两个主要文件组成：

词汇表
出现次数

在词汇表中提取文本中的常见单词（当然要过滤代词等黑名单单词）。出现次数文件保存单词和文档之间的连接（word1出现在doc1和doc2中，但不出现在doc3中）。它以矩阵形式表示。

Indexing process - inverted index

在上图中展示了创建所提到的两个文件的过程。

如果您对此问题进一步感兴趣，我可以向您推荐一本由Ricardo Yated撰写的优秀书籍 - 现代信息检索（在亚马逊上查看） - 大约在第200页左右。

希望能对您有所帮助 :-)

- Bery

1

这是一个非常好的答案，因为它解释了倒排索引的真正含义。它超越了正向索引和反向索引的概念，这与通过创建倒排索引实现搜索功能所使用的算法不同。 - AN6U5

1

我最喜欢这个答案，比这里的其他答案都好。我还要补充一点，你可以把倒排索引看作是一个去规范化的索引。一个单独的索引可以引用多个字段或实体，让你在单个查找中搜索许多内容（对于搜索引擎非常有用）。 - Miles B.

5

有许多类型的索引，例如B-tree、R-tree、哈希等等。为了不同的目的，我们必须选择正确的索引。

倒排索引是一种特殊的索引。倒排索引通常用于全文搜索引擎。使用倒排索引，我们可以尽快地找到一个单词在文档（或文档集）中的位置。考虑到内存和CPU的限制，其他索引无法完成这项工作。

您可以阅读Lucene文档以获取更多详细信息。它是一个开源搜索引擎。 http://lucene.apache.org/java/docs/index.html

- virushuo

2

在倒排索引中，我们有以下形式：

word1->出现在其中的文档列表（按顺序排序）

word2->出现在其中的文档列表（按顺序排序）

这对于搜索引擎查询处理非常有用，因为它允许我们找到单词出现的文档。

您可以使用监督机器学习来构建此倒排索引。

- Programmer

6

听起来像是一个索引，它有什么地方是倒置的呢？ - guidoism

2

@guidoism 反向索引是正向索引的倒置。正向索引为每个文档存储一个单词列表。例如：文档->w1，w2。 - Programmer

我仍然没有发现正向索引和倒排索引之间的任何区别（就它们的工作原理而言，不考虑命名）。对我来说，两者都像是将一个字段映射到一堆文档ID的索引。这就是我理解Oracle B树（也称为正向索引）如何组织数据的方式。我没有看到与倒排索引的原则有任何区别。在我的搜索中，将文档映射到w1、w2、w3似乎是一种低效的方法。想知道为什么首先要这样做？这让我回到了原点。 :-) - user1189332

@程序员快问一下：建立反向索引后，从正向索引文件中删除条目是否可行？ - Roy Lee

0

另一个区别：

与正向索引相比，使用倒排索引处理更新是昂贵的。

正向索引通过仅在相应文档索引中反映更改来轻松处理更新，而在倒排索引中，同一更改必须在倒排索引的多个位置上反映。

- Siva Kumar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jefflunt · Accepted Answer

一个常见的用途是"...允许快速全文搜索。"

这两种类型表示方向性。一种是通过索引向前移动，另一种是向后移动（反向）。就是这样，没有什么神秘的东西需要揭示。否则，这两种类型是相同的，只是问题在于你拥有哪些信息，以及因此你要查找哪些信息。

针对您的询问，我认为实际上没有办法知道为什么使用它今天是什么样子。唯一重要的是定义哪个是向前，哪个是倒置，这样我们就可以进行交谈，并且每个人都知道我们正在谈论的方向。想想“左”和“右”这些术语：它们是相对的。哪个是哪个并不重要，除了每个人都需要同意哪个是“左”哪个是“右”，以便这些单词具有含义。如果作为一种文化，我们决定翻转左和右，那么你将面临相同的问题，无法确定“右转”与“左转”的区别，因为约定的含义已经改变了。但是，命名是任意的，因此哪个是哪个（本身）并不重要，重要的是我们都同意其含义。

在你的评论中，你问道：“请不要仅仅定义这些术语”，你错过了重点，我认为你只是被措辞所困扰，实际上这两个术语之间没有任何区别。

为了方便未来的读者，我现在提供几个“正向”和“反向”索引的例子：

示例1：Web搜索

如果你认为倒排索引是数学中函数的反函数, 那么你就错了：在这里并不是这样。

在搜索引擎中，你有一个文档列表（网站页面），你输入一些关键词，然后得到结果。正向索引（或索引）是文档列表，以及它们中出现的单词。在Web搜索的示例中，Google爬行Web，构建文档列表，找出每个页面中出现的单词。倒排索引是单词列表，以及它们出现在哪些文档中。在Web搜索的示例中，你提供单词列表（搜索查询），Google生成文档（搜索结果链接）。

它们都是索引 - 只是一个问题，你走哪个方向。正向是从文档->到->单词，反向是从单词->到->文档。另一个例子是DNS查找（它接受主机名，并返回IP地址）和反向查找（它接受IP地址，并给出主机名）。书后的索引实际上是一个反向索引，如上面的例子所定义 - 一个单词列表，以及在书中找到它们的位置。在一本书中，目录就像一个正向索引：它是该书包含的文档（章节）列表，但不是列出这些部分中的单词，而是目录只给出了这些文档（章节）中所包含的名称/概述。你手机中的正向索引是你的联系人列表，以及与这些联系人相关联的电话号码（手机、家庭、工作）。反向索引是允许你手动输入电话号码的东西，当你点击“拨号”时，你会看到这个人的名字，而不是号码，因为你的手机已经取得了电话号码并找到了与之关联的联系人。