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

这里有一篇相当不错的文章: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上有一个更新的版本,但它似乎有更少的信息比旧的.

简而言之,当lucene索引文档时,它会将其分解为多个术语.然后,它将这些术语存储在索引文件中,其中每个术语与包含它的文档相关联.您可以将其视为有点像哈希表.

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

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

Answer 2

简而言之,Lucene使用磁盘上的Skip-Lists 构建倒排索引,然后使用有限状态传感器(FST)将索引术语的映射加载到内存中.但请注意,Lucene 并不(必然)将所有索引术语加载到RAM中,正如Lucene索引系统本身的作者Michael McCandless所描述的那样.请注意,通过使用Skip-Lists,可以从一个匹配到另一个匹配遍历索引,从而使得set,特别是范围查询成为可能(很像B-Trees).关于索引Skip-Lists的Wikipedia条目也解释了为什么Lucene的Skip-List实现被称为多级 Skip-List - 实质上是为了使查找成为可能(再次,就像B-Trees一样).O(log n)

因此,一旦基于Skip-List数据结构的反转(term)索引是从文档构建的,索引就存储在磁盘上.Lucene的那么负载(前面已经说了:可能的话,只有一些),这些条款为有限状态传感器,在FST实施宽松的启发由Morfologick.

Michael McCandless(也)解释了Lucene如何以及为什么使用(最小非循环)FST来索引Lucene存储在内存中的术语,基本上作为a SortedMap<ByteSequence,SomeOutput>,并给出了FST如何工作的基本思路(即, FST如何压缩字节序列[即,索引术语]以使该映射的存储器使用变得亚线性化.他指出了描述 Lucene使用的特定FST算法的论文.

对于那些好奇为什么Lucene使用Skip-Lists,而大多数数据库使用(B +) - 和/或(B)-Trees,请看一下关于这个问题的正确的答案(Skip-Lists vs. B-Trees).这个答案提供了一个非常好的,深刻的解释 - 基本上,并没有那么多使得索引的并发更新"更容易"(因为你可以决定不立即重新平衡B树,从而获得与a-a相同的并发性能) Skip-List),但是,Skip-Lists可以让您不必处理 B-Trees所需的(延迟的或非平衡的)平衡操作(最终)(事实上,正如答案显示/引用,可能很少) B-Trees和[多级] Skip-Lists之间的性能差异,如果其中任何一个"完成正确".)

Answer 3

似乎你的问题更多的是关于索引合并而不是关于索引本身.

如果忽略底层细节,索引过程非常简单.Lucene从文档中形成所谓的"倒排索引".因此,如果带有文本"要成为或不成为"且id = 1的文档进入,则反向索引将如下所示:

[to] ? 1
[be] ? 1
[or] ? 1
[not] ? 1

这基本上就是 - 从单词到包含给定单词的文档列表的索引.该索引(单词)的每一行称为发布列表.这个指数在长期存储中持续存在.

实际上事情当然更复杂:

• Lucene可能会根据给定的特定分析器跳过一些单词;
• 可以使用词干算法对单词进行预处理,以减少语言的弹性;
• 收录列表可以不仅包含了文档的标识,也抵消了里面的文件给定字(潜在的多个实例)和一些其他附加信息.

还有许多并发症对于基本理解而言并不那么重要.

但重要的是要理解,Lucene索引只是附加.在某些时间点,应用程序决定提交(发布)索引中的所有更改.Lucene用索引完成所有服务操作并关闭它,因此它可用于搜索.提交索引后基本上是不可变的.该索引(或索引部分)称为段.当Lucene执行搜索查询时,它会搜索所有可用的段.

所以问题出现了 - 我们怎样才能改变已编入索引的文件？

新索引文档的新文档或新版本将在新段中编入索引,旧版本在之前的段中使用所谓的杀死列表无效.杀戮列表是可以更改的已提交索引的唯一部分.正如您可能猜到的,索引效率会随着时间的推移而下降,因为旧索引可能包含大部分已删除

这就是合并的地方.合并 - 是将多个索引组合在一起以提高整体效率的过程.在合并期间基本上发生的是复制到新段的实时文档和完全删除的旧段.

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

希望它会有所帮助.

Answer 4

它是反向索引,但是没有指定它使用的结构. lucene中的索引格式具有完整的信息.
从"文件扩展名摘要"开始.

你会首先注意到它涉及各种不同的索引.据我所知,这些都没有严格使用B树,但有相似之处 - 上述结构确实类似树木.