arrays - 为什么 Lucene 使用数组而不是哈希表作为倒排索引？

Question

我在看阿德里安·格兰德的 talk on Lucene's index architecture他提出的一点是 Lucene 使用排序数组来表示其倒排索引的字典部分。使用排序数组而不是哈希表(“经典”倒排索引数据结构)背后的原因是什么？

哈希表提供 O(1) 插入和访问，在我看来这对快速处理查询和合并索引段有很大帮助。另一方面，排序数组只能提供 O(logN) 访问和 (gasp) O(N) 插入，尽管合并 2 个排序数组与合并 2 个哈希表的复杂度相同。

我能想到的哈希表的唯一缺点是更大的内存占用(这确实可能是一个问题)和更少的缓存友好性(尽管查询排序数组之类的操作需要二进制搜索，这与缓存不友好一样)。

那么这是什么一回事？ Lucene 开发人员使用数组肯定有很好的理由。这与可扩展性有关吗？磁盘读取速度？完全是别的什么？

Answer 1

好吧，我会在这里推测(可能应该是评论 - 但它会太长)。

HashMap通常是具有搜索时间的快速查找结构O(1) - 意味着它是恒定的。但那是一般情况；因为(至少在 Java 中)一个 HashMap用途 TreeNodes - 搜索是 O(logn)在那个桶里面。即使我们认为他们的搜索复杂度是 O(1) ，这并不意味着它同时是明智的。它只是意味着它对于每个单独的数据结构都是恒定的。

内存确实-我举个例子here .总之收藏15_000_000条目需要多一点 1GB内存；排序后的数组可能更紧凑，特别是因为它们可以保存基元而不是对象。

将条目放入 HashMap (通常)需要重新散列所有键，这可能会对性能造成重大影响，因为它们都必须潜在地移动到不同的位置。

这里可能还有一点 - 在范围内搜索，这需要一些 TreeMap可能， wheres 数组更适合这里。我正在考虑对索引进行分区(可能是他们在内部进行)。

我和你有同样的想法——数组通常是连续的内存，可能更容易被 CPU 预取。

最后一点:把我放在他们的鞋子里，我会从 HashMap 开始首先......我相信他们的决定有令人信服的理由。我想知道他们是否有实际测试来证明这个选择。