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

Question

我正在观看Adrien Grand关于Lucene索引架构的讲座，他提到Lucene使用排序数组来表示其倒排索引的字典部分。为什么要使用排序数组而不是哈希表（“经典”的倒排索引数据结构）呢？

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

我能想到哈希表的唯一缺点是占用更大的内存空间（这确实可能是一个问题），并且不太友好缓存（尽管像查询排序数组这样的操作需要二进制搜索，这也是同样不友好的缓存）。

那么怎么办？Lucene开发人员一定有使用数组的非常好的理由。是与可扩展性有关吗？磁盘读取速度？还是其他原因？

- CoconutFred

---

很棒的问题！ - Eugene

@Ivan在这个回答中提供了多个Lucene不使用哈希表的原因：https://dev59.com/dqfja4cB1Zd3GeqP2uQm#48053519 - xpages-noob

Answer 1

我不是专家，但我可以猜测（可能应该写成注释，但这会太长）。

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

2. 内存 - 我将在这里给出一个例子。简而言之，存储 15_000_000 条记录需要略微超过 1GB 的 RAM; 排序后的数组可能更紧凑，尤其是它们可以容纳原始类型而非对象。

3. 将条目放入 HashMap（通常）需要重新哈希 所有 关键字，这可能会导致显著的性能损耗，因为它们都有可能移动到不同的位置。

4. 也许还有一个额外的要点 - 搜索范围，这可能需要一些 TreeMap，而数组在这里更加适合。我考虑划分索引（也许他们在内部执行此操作）。

5. 我和你的想法一样 - 数组通常是连续的内存，对 CPU 来说预取非常容易。

6. 最后一点：如果换做是我，我会首先尝试使用 HashMap……我确信他们选择这种方法是有充分的理由的。我想知道他们是否有实际的测试来证明这个决定。

- Eugene

---

谢谢你的回答！我认为这也可能与Lucene需要泛化到不仅仅是文本术语有关，而对任意术语进行哈希可能会产生很大的影响。但我会尝试做一个小实验，看看HashMap和数组在文本索引方面的比较。 - CoconutFred

不要忘记它们设置的不可变性。 - Anthony De Meulemeester

@AnthonyDeMeulemeester 我完全不知道lucene是如何设置的，零基础，谢谢您的反馈。 - Eugene

Lucene为您索引的每个文档创建一个段，当段数过多时，它们会合并成一个段。这使得它是不可变的，因为它们不会更新现有的内存。 - Anthony De Meulemeester

Answer 2

我在思考它的原因。只是想到了一个在文本搜索上下文中非常重要的用例。但我可能完全错了 :)

为什么使用排序数组而不是字典？

是的，它在范围查询上表现良好，但我认为Lucene主要是为文本搜索而构建的。现在想象一下，如果您要搜索基于前缀的查询，例如：country:Ind*，则需要扫描整个HashMap/字典。而如果您有一个排序数组，则这将变为log(n)。

由于我们有一个排序数组，更新数组将效率低下。因此，在Lucene中，段（倒排索引驻留在段中）是不可变的。

- Bikas Katwal