algorithm - lucene如何索引文件？

Question

我阅读了一些关于 Lucene 的文档；我也阅读了此链接中的文档(http://lucene.sourceforge.net/talks/pisa)。

我真的不明白 Lucene 是如何索引文档的，也不明白 Lucene 使用哪些算法来建立索引？

在上面的链接中，它说 Lucene 使用此算法进行索引:

• incremental algorithm:
  • maintain a stack of segment indices
  • create index for each incoming document
  • push new indexes onto the stack
  • let b=10 be the merge factor; M=8

---

for (size = 1; size < M; size *= b) {
    if (there are b indexes with size docs on top of the stack) {
        pop them off the stack;
        merge them into a single index;
        push the merged index onto the stack;
    } else {
        break;
    }
}

该算法如何提供优化的索引？

Lucene是使用B-tree算法还是其他类似的算法进行索引- 或者它是否有特定的算法？

Answer 1

简而言之，Lucene 使用Skip-Lists 构建倒排索引。 在磁盘上，然后使用 Finite State Transducer 将索引项的映射加载到内存 (FST)。但是请注意，Lucene does not (necessarily) load all indexed terms to RAM ，正如 Lucene 索引系统的作者 Michael McCandless 所描述的那样。请注意，通过使用 Skip-Lists，索引可以从一次命中遍历到另一次命中，从而使 set 和特别是 range queries 成为可能(很像 B 树).和 Wikipedia entry on indexing Skip-Lists还解释了为什么 Lucene 的 Skip-List 实现被称为多级 Skip-List - 本质上是为了制作 O(log n)查找可能(同样，很像 B 树)。

所以一旦倒排(术语)索引 - 它基于 Skip-List data structure - 由文件建立，索引存储在磁盘上。然后，Lucene 将这些术语加载(如前所述:可能只有一部分)到 Finite State Transducer 中。 , 在 FST 实现中 loosely inspired通过 Morfologick .

Michael McCandless(也)在 explaining how and why Lucene uses a (minimal acyclic) FST 方面做得非常好且简洁。索引存储在内存中的 Lucene 术语，本质上是一个 SortedMap<ByteSequence,SomeOutput> ，并给出了 FST 如何工作的基本概念(即，FST 如何压缩字节序列 [即，索引项] 以使此映射的内存使用增长为次线性)。他指向the paper that describes the particular FST algorithm Lucene 也使用。

对于那些好奇为什么 Lucene 使用 Skip-Lists 而大多数数据库使用 (B+)- 和/或 (B)-Trees 的人，请查看 the right SO answer关于这个问题(Skip-Lists vs. B-Trees)。这个答案给出了一个很好的、深入的解释——本质上，不是使索引的并发更新“更容易接受”(因为你可以决定不立即重新平衡 B 树，从而获得与 Skip-List 大致相同的并发性能)，而是 Skip-List 使您不必处理(延迟或不延迟)平衡操作(最终) B-Trees 需要(事实上，正如答案所示/引用，B-Trees 和[多级] 跳过列表之间的性能差异可能非常小，如果其中任何一个“正确完成”。)