lucene - 如何在 Lucene 文档中定义主键字段以获得最佳查找性能？

Question

在我的 Lucene 索引 (v7.2) 中创建文档时，我添加了 uid包含唯一 id/key(字符串)的字段:

doc.add(new StringField("uid",uid,Field.Store.YES))

为了稍后检索该文档，我为给定的唯一 id 创建了一个 TermQuery 并使用 IndexSearcher 进行搜索:

searcher.search(new TermQuery(new Term("uid",uid)),1)

作为一个Lucene“新手”，我想知道以下几点:

我应该如何改进这种方法以获得最佳查找性能？
例如，如果我将唯一 id 存储为
一个字节数组而不是一个字符串？或者是否有一些可以使用的特殊编解码器或过滤器？

通过唯一 ID 查找文档的时间复杂度是多少？ 由于索引至少包含每个文档的一个唯一术语，查找时间将随文档数量 (O(n)) 呈线性增加，对吗？

Answer 1

理论

有一个blog post关于 Lucene 术语索引和查找性能。它清楚地揭示了按 id 查找文档的复杂性的所有细节。这篇文章很旧，但从那以后没有任何改变。

以下是与您的问题相关的一些重点:

Lucene 是一个搜索引擎，其中检索的最小元素是文本术语，因此这意味着:二进制、数字和字符串字段在 BlockTree terms dictionary 中表示为字符串。 .

通常，查找的复杂性取决于术语长度:Lucene 使用内存中的前缀-trie 索引结构来执行术语查找。由于现实世界的硬件和软件实现的限制(为了避免超大尝试的多余磁盘读取和内存溢出)，Lucene 使用了 BlockTree 结构。这意味着它将prefix-trie 以小块的形式存储在磁盘上，并且一次只加载一个块。这就是为什么以易于阅读的顺序生成 key 如此重要的原因。那么让我们按照影响程度来排列这些因素:

术语的长度 - 要加载更多块

术语的模式 - 避免多余的阅读

术语计数 - 减少块计数

算法和复杂性

让 term 是单个字符串，让 term dictionary 是一个大的术语集。如果我们有一个术语字典，并且我们需要知道字典中是否有单个术语，trie(和最小确定性非循环有限状态自动机(DAFSA)作为子类)是可以帮助我们的数据结构。关于你的问题:“如果哈希查找可以做同样的事情，为什么要使用尝试？”，这里有几个原因:

尝试可以在 O(L) 时间内找到字符串(其中 L 表示单个术语的长度)。与最坏情况下的哈希表(哈希表在哈希冲突和复杂的哈希算法(如 MurmurHash3)的情况下需要线性扫描)相比，这要快一些，或者在完美情况下类似于哈希表。

哈希表只能找到与我们正在寻找的单个术语完全匹配的字典术语；而特里树允许我们找到具有单个不同字符、共同前缀、缺少字符等的术语。

树可以按键提供条目的字母顺序，因此我们可以按字母顺序枚举所有术语。

trie(尤其是 DAFSA)提供了非常紧凑的术语表示和重复数据删除。

以下是 3 个术语的 DAFSA 示例:bath、bat 和 batch:


在键查找的情况下，请注意降低自动机(或 trie)中的单个级别是在恒定时间内完成的，并且每次算法降低自动机(trie)中的单个级别时，都会从术语中删除一个字符，因此我们可以得出结论，可以在 O(L) 时间内完成在自动机 (trie) 中找到一项。