我看了Adrien Grand的talk on Lucene's index architecture，他提出的一个观点是Lucene使用排序数组来表示其倒排索引的字典部分。使用排序数组而不是哈希表（“经典的”倒排索引数据结构）背后的原因是什么？
哈希表提供了O（1）的插入和访问，这对快速处理查询和合并索引段有很大帮助。另一方面，排序数组只能提供O（logN）的访问和O（N）的插入，尽管合并2个排序数组和合并2个哈希表一样复杂。
我能想到的哈希表的唯一缺点是内存占用更大（这确实可能是个问题）和缓存友好性更低（尽管像查询排序数组这样的操作需要折半搜索，这也是缓存不友好的）。
那么，这是怎么回事呢？Lucene开发人员使用阵列肯定有很好的理由。是与可伸缩性有关吗？磁盘读取速度？还是完全其他的什么？
2条答案
按热度按时间jqjz2hbq1#
好吧，我将在这里 * 推测 *（可能应该是一个评论-但它会太长）。
HashMap通常是具有搜索时间O(1)的快速查找结构，这意味着它是恒定的。因为（至少在Java中）一个HashMap使用TreeNodes--在那个桶中搜索是O(logn)。即使我们认为它们的搜索复杂度是O(1)，这并不意味着它们在时间上是 * 相同的 *，它只是意味着对于每个单独的数据结构来说它是恒定的。1.内存确实如此--我将在这里给予一个例子。简而言之，存储
15_000_000条目需要比1GB多一点的RAM;排序后的数组可能更加紧凑，特别是因为它们可以保存原语而不是对象。1.将条目放入
HashMap（通常）需要对 * 所有 * 键进行重新散列，这可能会严重影响性能，因为它们可能都必须移动到不同的位置。1.这里可能还有一点--在范围内搜索，这可能需要一些
TreeMap，而数组更适合这里。我正在考虑对索引进行分区（可能是在内部进行）。1.我和你有同样的想法--数组通常是连续的内存，可能更容易被CPU预取。
1.还有最后一点：把我放在他们的位置上，我会先从X1 M10 N1 X开始...我相信他们的决定有令人信服的理由。我想知道他们是否有实际的测试来证明这个选择。
cnwbcb6i2#
我在想它背后的原因。只是想到了一个在文本搜索环境中很重要的用例。我可能完全错了：）
为什么是排序数组而不是字典？
是的，它在范围查询上表现得很好，但是IMO Lucene主要是为文本搜索构建的。
country:Ind*，你需要扫描整个HashMap/Dictionary，而如果你有一个排序的数组，这就变成log（n）。因为我们有一个排序的数组，所以更新数组的效率很低。因此，在Lucene中，段（倒排索引驻留在段中）是不可变的。