Lucene 索引文档怎么样？

我阅读了一些关于 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;
}
}

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

Does Lucene use B-tree algorithm or any other algorithm like that for indexing 还是有特定的算法？

90920 次浏览
小开

它是 反向指数反向指数，但是没有指定它使用的结构。 Lucene 中的索引格式具有完整的信息。
Start with 'Summary of File Extensions'.

您首先会注意到，它讨论了各种不同的索引。 As far as I could notice none of these use strictly speaking a B-tree, but there are similarities - the above structures do resemble trees.

小开

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

编辑12/2014: 由于原始版本被删除而更新到存档版本，可能最近的替代方案是 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上有一个更新的版本，但是它似乎比旧版本有更少的信息。

In a nutshell, when lucene indexes a document it breaks it down into a number of terms. It then stores the terms in an index file where each term is associated with the documents that contain it. You could think of it as a bit like a hashtable.

术语是使用一个分析器生成的，该分析器将每个单词的词根形式分解为词根形式。英语中最流行的词干分析算法是 Porter 词干分析算法: http://tartarus.org/~martin/PorterStemmer/

当发出一个查询时，它将通过用于构建索引的同一个分析器进行处理，然后用于在索引中查找匹配的术语。提供与查询匹配的文档列表。

小开

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

如果忽略低级别的细节，索引过程非常简单。Lucene 从文档中形成了所谓的“反向索引”。因此，如果文档中有文本“ To be or not To be”和 id = 1，那么反向索引看起来应该是这样的:

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

基本上就是这样——包含给定单词的文档从单词到 名单的索引。这个索引(单词)的每一行称为发布列表。这个索引将保存在长期存储中。

当然，实际情况要复杂得多:

  • 基于给定的特定分析器，Lucene 可能会跳过一些单词;
  • 采用词干提取算法对单词进行预处理，降低了语言的灵活性;
  • 张贴列表不仅可以包含文档的标识符，还可以包含文档内给定单词的偏移量(可能有几个实例)和其他一些附加信息。

还有更多的复杂情况，对于基本的理解并不那么重要。

尽管如此，理解 Lucene 指数是 附录还是很重要的。在某个时间点，应用程序决定提交(发布)索引中的所有更改。Lucene 使用 index 完成所有服务操作并关闭它，因此可以进行搜索。提交索引后基本不变。这个索引(或索引部分)称为 片段。当 Lucene 执行查询搜索时，它会搜索所有可用的段。

所以问题来了，我们怎样才能 更改已编入索引的文档？

使用所谓的 暗杀名单，新文档或已经索引的文档的新版本在新段中建立索引，而旧版本在以前的段中无效。杀死列表是提交索引中唯一可以更改的部分。正如您可能猜到的，索引效率随着时间的推移而下降，因为旧的索引可能包含大部分已删除的文档。

This is where merging comes in. Merging – is the process of combining several indexes to make more efficient index overall. What is basically happens during merge is live documents copied to the new segment and old segments removed entirely.

Using this simple process Lucene is able to maintain index in good shape in terms of a search performance.

希望能有所帮助。

小开
最佳答案

简而言之，Lucene 使用 < strong > 跳过列表 on disk构建一个反向索引，然后使用 有限状态传感器(FST)加载索引术语 变成记忆的映射。然而，请注意 Lucene 不(必然)将所有索引术语加载到 RAM，正如 Lucene 索引系统的作者 Michael McCandless 所描述的那样。注意，通过使用 Skip-List，索引可以从一个命中遍历到另一个命中，使得像 准备好了这样的事情成为可能，特别是 range queries(非常类似于 B 树)。而且，关于索引跳过的 Wikipedia 条目-列表还解释了为什么 Lucene 的 Skip-List 实现被称为 多层次 Skip-List ——本质上是为了使 O(log n)查找成为可能(同样，非常类似于 B-Tree)。

因此，一旦从文档构建了基于 跳过-列表数据结构的反向(术语)索引，索引就存储在磁盘上。然后 Lucene 加载(如前所述: 可能，只是一部分)这些术语到 Finite State Transducer中，在 Morfologick的 FST 实现 灵感不足中。

Michael McCandless (同样)做了一个相当好的简洁的 解释 Lucene 如何以及为什么使用(最小无环) FST工作来索引 Lucene 存储在内存中的术语，本质上是一个 SortedMap<ByteSequence,SomeOutput>，并且给出了 FST 如何工作的基本概念(例如，FST 如何压缩字节序列(例如，索引术语) ，使内存使用这个映射成长为次线性)。他还指出了 Lucene 使用的 the paper that describes the particular FST algorithm。

对于那些好奇为什么 Lucene 使用跳过列表，而大多数数据库使用(B +)-和/或(B)-树的人，看看关于这个问题的 右边的回答(跳过列表与 B-树)。这个答案给出了一个相当好的、深刻的解释——本质上，没有使索引的并发更新变得“更易于接受”(因为你可以决定不立即重新平衡一个 B-Tree，从而获得与 Skip-List 大致相同的并发性能) ，而是 B-Tree 所需要的 跳过列表使您不必在(延迟或不延迟) 平衡操作(最终)(事实上，正如答案显示/引用，如果 B-Tree 和[多级] Skip-List 都“做对了”，那么它们之间的性能差异可能很小)


提交答案