哈希索引 vs 倒排索引

Question

据我理解，哈希/倒排索引将值/单词映射到记录/文档。然而，哈希索引的插入复杂度较低（在溢出时添加新的存储桶），但倒排索引的插入复杂度较高（因为需要维护文档ID的排序列表）。这是否意味着它们本质上是相同的，只是实现方式不同？

- Kushal Bansal

---

似乎你在谈论某种特定的技术，但没有命名它并放置标签。 - leventov

我正在谈论关系数据库中哈希索引和网络文档搜索中的倒排索引的使用。让我看看是否可以添加它们的标签。 - Kushal Bansal

Answer 1

据我所知，哈希索引与倒排索引在使用情况/场景上完全不同。哈希索引仅是从索引键到内存中给定行的确切位置的映射（主要用于关系数据库中的内存优化表），而倒排索引实际上是从单词到包含它的文档的映射。

因此，如果我们看一下，一个单词可能包含在许多文档中，而这些文档将被许多这样的单词共享。因此，在倒排索引的情况下，许多键指向文档ID，这些文档ID在许多这样的键之间是共同的，而在哈希索引的情况下，键指向的数据，即行数据可能完全不相关。

因此，它们并不相同，因为它们处理完全不相关的情况，并且实现方式也非常不同。

有关倒排索引的更多信息，您可以参考此处的文章：BigData: Inverted Index

- Abhishek Jain

Answer 2

一个倒排索引是一种数据结构，将内容（如标记）映射到文档中的位置。倒排索引的主要优点是不必搜索整个数据集以查找有趣的文档。

考虑一本书。它末尾的索引是倒排索引的一个例子。但它不是哈希索引。

哈希索引是使用哈希表实现的倒排索引。这张图片展示了它们如何存储数据：

其他数据结构可以用于实现倒排索引，例如树。二叉树可以使用，但通常过于简单，因此使用红黑树或B树。基于树的索引有点难以理解，因此图片并没有太大帮助。它们具有使它们比哈希索引更可取的属性，例如在拥有大量数据时更容易更新和具有更好的最坏情况性能。

- Björn Lindqvist

Answer 3

倒排索引只是一个概念（与正向索引相反）。它涉及到将单词或文档作为键值对中的键。

哈希表只是索引的一种实现方式，可以替代树等其他实现方式。

因此，您可以使用哈希表实现倒排索引。您也可以使用树来实现倒排索引。

哈希索引的插入复杂度较低（在溢出时仅添加新的桶），但倒排索引的复杂度较高（由于需要维护文档ID的排序列表）

对于倒排索引，维护排序列表是可选的。仅当搜索引擎支持高级功能（例如搜索多个连续单词）时才需要。

甜苹果很甜。它生长在苹果树上。我喜欢吃甜苹果。

Sweet: 1, 4, 13
Apple: 2, 9, 14


Query: "Sweet Apple"
Returns (1,2), (13,14)

---

因此，对于支持连续单词搜索的全文搜索引擎，使用哈希表实现的倒排索引仍然必须对桶条目进行排序。因此，在这种用例中使用哈希表实现索引树并没有任何优势。

- Raymond Pang