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

Question

我正在观看Adrien Grand 关于Lucene索引架构的演讲,他提出的一点是Lucene使用排序数组来表示其倒排索引的字典部分.使用排序数组而不是哈希表("经典"反向索引数据结构)背后的原因是什么？

散列表提供O(1)插入和访问,对我来说,似乎它可以帮助快速处理查询和合并索引段.另一方面,排序的数组只能提供O(logN)访问和(gasp)O(N)插入,尽管合并2个排序的数组与合并2个哈希表的复杂性相同.

我能想到的散列表的唯一缺点是更大的内存占用(这可能确实是一个问题)和更少的缓存友好性(尽管像查询排序数组这样的操作需要二进制搜索,这就像缓存不友好一样).

那么这是什么一回事？Lucene开发人员必须有一个很好的理由使用数组.这与可扩展性有关吗？磁盘读取速度？还有别的吗？

Answer 1

好吧，我会在这里推测（可能应该是一个评论 - 但它会太长）。

1. HashMap通常是一个具有搜索时间的快速查找结构O(1)- 这意味着它是恒定的。但这是一般情况；因为（至少在 Java 中）aHashMap使用TreeNodes- 搜索位于O(logn)该存储桶内。即使我们认为它们的搜索复杂度是O(1)，也不意味着它们在时间上是相同的。它只是意味着它对于每个单独的数据结构都是恒定的。

2. 记忆确实——我在这里举一个例子。简而言之，存储15_000_000条目需要稍微多一点1GB的 RAM；排序后的数组可能更加紧凑，特别是因为它们可以保存基元而不是对象。

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

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

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

6. 最后一点：把我放在他们的立场上，我会从第一个开始HashMap......我确信他们的决定有令人信服的理由。我想知道他们是否有实际测试来证明这个选择。