full-text-search - 哈希索引与倒排索引

Question

据我了解，哈希/倒排索引将值/单词分别映射到记录/文档。但是，哈希索引中的插入复杂度很低（因为它会在溢出的情况下添加一个新的桶），但倒排索引中的插入复杂度更高（由于维护文档 ID 的排序列表）。这是否意味着它们本质上是相同的，除了实现？

Answer 1

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

因此，如果我们看一下，一个词可能包含在许多文档中，并且这些文档将被许多这样的词共享。因此，在倒排索引的情况下，许多键指向在许多此类键中通用的文档 ID，而在散列索引的情况下，键指向的数据（即行数据）可能彼此完全不相关。

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

有关倒排索引的更多信息，您可以参考这里的帖子：BigData: Inverted Index

Answer 2

倒排索引是一种将内容（例如标记）映射到它们在文档中的位置的数据结构。倒排索引的主要好处是不必搜索整个数据集合来查找有趣的文档。

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

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

其他数据结构可用于实现倒排索引，例如树。可以使用二叉树，但通常过于简单，因此使用 rb-trees 或 b-trees。基于树的索引有点难以理解，所以图片没有多大帮助。当您拥有大量数据时，它们具有使它们比基于哈希的索引更受欢迎的属性，例如更容易更新和具有更好的最坏情况性能。