lucene如何索引文件？

Question

我读了一些关于Lucene的文档;我还阅读了链接 （http://lucene.sourceforge.net/talks/pisa）中的文档。

我真的不明白，索引如何Lucene的文件，不明白哪种算法使用的Lucene索引？

在上述链接，它说Lucene的使用此算法用于索引：

• 增量算法：
  • 维持段索引的堆叠
  • 对于每个传入文档
  创建索引
  • 推新的索引送到堆栈
  • 令b = 10是合并因子; 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树算法或任何其他算法类似的索引 - 或者它是否有一个特定的算法？

Answer 1

这是inverted index，但这并不说明它用的结构。 Index format in lucene有完整的信息。
从'文件扩展名摘要'开始。

你会首先注意到的是它谈论各种不同的指标。 至于我能看到这些没有使用严格说来B-tree的，但也有相似之处 - 上述结构做类似的树。

Answer 2

有一个相当不错的文章在这里：https://web.archive.org/web/20130904073403/http://www.ibm.com/developerworks/library/wa-lucene/

编辑二千零十四分之一十二：更新为存档版本由于原来被删除，可能是最好的最近的选择是http://lucene.apache.org/core/3_6_2/fileformats.html

还有一个更近版本号为http://lucene.apache.org/core/4_10_2/core/org/apache/lucene/codecs/lucene410/package-summary.html#package_description，但它的信息似乎比较旧的信息要少。

简而言之，当lucene索引一个文档时，它会将其分解成若干项。然后将这些条款存储在索引文件中，其中每个条款与包含它的文件相关联。你可以认为它有点像散列表。

使用分析器生成术语，该分析器将每个单词词根化为它的根形式。用于英语的最流行的词干算法是波特干扰算法：http://tartarus.org/~martin/PorterStemmer/

当发出查询时，它通过用于构建索引并且用于查找匹配项的相同分析器来处理（s ）在索引中。这提供了与查询相匹配的文档列表。

Answer 3

看来你的问题更多地是关于索引合并而不是索引本身。

如果您忽略低级别详细信息，索引过程非常简单。 Lucene从文档中形成所谓的“倒排索引”。所以，如果用文本文档“生存还是毁灭”和id = 1进来，倒排索引会是什么样子：

[to] → 1 
[be] → 1 
[or] → 1 
[not] → 1 

这基本上是它 - 从词的索引文件的列表包含给定的词。此索引（单词）的每一行称为发布列表。这个指数在长期储存中仍然存在。

在当然的事情现实更为复杂：

• Lucene的可以跳过基于给定的具体分析一些话;
• 单词可以使用词干算法进行预处理，以减少语言的灵活性;
• 发布列表不仅可以包含文档的标识符，还可以包含文档中给定单词的偏移量（可能包含多个实例）以及一些其他附加信息。

还有很多并发症对于基本的了解并不那么重要。

尽管Lucene索引是仅附加，但理解这一点很重要。在某些时间点，应用程序决定提交（发布）索引中的所有更改。 Lucene使用索引完成所有服务操作并关闭它，因此可用于搜索。提交索引后基本上是不可变的。该索引（或索引部分）被称为段。当Lucene执行搜索查询时，它会搜索所有可用的段。

所以问题出现了 - 我们如何改变已经索引的文件？

使用所谓的杀死列表，新文档或已编入索引的文档的新版本在新分段和旧版本中失效的索引。杀死列表是可以改变的承诺索引的唯一部分。正如您猜测的那样，索引效率随着时间而下降，因为旧索引可能包含大部分已删除的文档。

这是合并进来的地方。合并 - 合并多个索引以整体提高索引效率的过程。合并过程中基本上会发生的情况是，将活动文档复制到新分段，并将旧分段完全删除。

使用这个简单的过程Lucene能够在搜索性能方面保持良好的索引。

希望它会有所帮助。

Answer 4

概括地说，Lucene的构建在磁盘使用Skip-Lists倒排索引，并且然后使用一个Finite State Transducer（FST）加载的索引术语映射到内存。然而请注意，Lucene does not (necessarily) load all indexed terms to RAM，正如Michael McCandless所描述的，Lucene的索引系统本身的作者。请注意，通过使用跳过列表，索引可以从一个命中遍历到另一个命中，使得类似设置，特别是范围查询可能（很像B树）。 Wikipedia entry on indexing Skip-Lists也解释了为什么Lucene的Skip-List实现被称为多级跳过列表 - 实质上，使O(log n)查找成为可能（再次，很像B-Trees）。

因此，一旦从文档构建基于Skip-List data structure的反转（term）索引，索引就存储在磁盘上。然后Lucene将这些条件加载到Finite State Transducer中（如前所述：可能只有一些），在FST实现loosely inspired中加载Morfologick。

迈克尔·麦卡（也）做的explaining how and why Lucene uses a (minimal acyclic) FST一个不错的和简洁的工作来索引项的Lucene在内存中存储，基本上为SortedMap<ByteSequence,SomeOutput>，并给出了FSTS如何工作（即，如何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树，从而获得大致相同的并发性能作为跳过列表），而是，跳过列表可以让您不必延迟工作（延迟或不延迟）平衡操作（最终）需要B-Trees（实际上，因为答案显示/引用，如果其中任何一个都是“正确的”，那么B-Trees和[多级] Skip-Lists之间的性能差别可能很小。）