我正在观看Adrien Grand 关于Lucene索引架构的演讲,他提出的一点是Lucene使用排序数组来表示其倒排索引的字典部分.使用排序数组而不是哈希表("经典"反向索引数据结构)背后的原因是什么？
散列表提供O(1)插入和访问,对我来说,似乎它可以帮助快速处理查询和合并索引段.另一方面,排序的数组只能提供O(logN)访问和(gasp)O(N)插入,尽管合并2个排序的数组与合并2个哈希表的复杂性相同.
我能想到的散列表的唯一缺点是更大的内存占用(这可能确实是一个问题)和更少的缓存友好性(尽管像查询排序数组这样的操作需要二进制搜索,这就像缓存不友好一样).
那么这是什么一回事？Lucene开发人员必须有一个很好的理由使用数组.这与可扩展性有关吗？磁盘读取速度？还有别的吗？