散列索引与倒排索引

Question

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

Answer 1

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

因此，如果我们看一下它，一个单词可以包含在许多文档中，这些文档将由许多这样的单词共享。因此，在倒排索引的情况下，许多键指向文档in，而在散列索引的情况下，键所指向的数据，即行数据可能彼此完全不相关。

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

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

Answer 2

倒排索引是一种数据结构，它将内容(如令牌)映射到它们在文档中的位置。倒排索引的主要好处是，不必搜索整个数据集合来查找感兴趣的文档。

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

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

​

​

可以使用其他数据结构来实现倒排索引，例如树。可以使用二叉树，但通常过于简单，因此使用rb树或b树。基于树的索引比较难理解，所以图片不会有太大帮助。当您有大量数据时，它们的属性使它们比基于散列的索引更可取，例如更容易更新，并在最坏情况下具有更好的性能。