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

Question

在我的 Lucene 索引 (v7.2) 中创建文档时，我uid向其中添加了一个包含唯一 ID/键（字符串）的字段：

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

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

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

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

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

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

Answer 1

理论

\n\n

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

\n\n

以下是与您的问题相关的一些要点：

\n\n

\n
• Lucene 是一个搜索引擎，检索的最小元素是文本术语，因此这意味着：二进制、数字和字符串字段在BlockTree 术语字典中表示为字符串。
\n
• 一般来说，查找的复杂度取决于术语长度：Lucene 使用内存中的前缀特里索引结构来执行术语查找。由于现实世界的硬件和软件实现的限制（为了避免过多的磁盘读取和超大尝试的内存溢出），Lucene使用了BlockTree结构。这意味着它将前缀特里树以小块的形式存储在磁盘上，并且一次仅加载一个块。这就是为什么以易于阅读的顺序生成密钥如此重要的原因。那么让我们根据影响程度来排列这些因素：\n\n
  \n
  • 术语长度 - 要加载更多块
  \n
  • 术语的模式 - 避免多余的读取
  \n
  • 术语计数 - 减少块计数
  \n
\n

\n\n

算法和复杂性

\n\n

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

\n\n

\n
• 尝试可以在 O(L) 时间内找到字符串（其中 L 表示单个术语的长度）。与最坏情况下的哈希表相比（哈希表需要线性扫描以防哈希冲突以及像 MurmurHash3 这样的复杂哈希算法），或者类似于完美情况下的哈希表，这要快一些。
\n
• 哈希表只能找到与我们要查找的单个术语完全匹配的字典术语；而 trie 允许我们找到具有单个不同字符、共同前缀、缺少字符等的术语。
\n
• trie 可以按键提供条目的字母顺序排序，因此我们可以按字母顺序枚举所有术语。
\n
• trie（尤其是 DAFSA）通过重复数据删除提供了非常紧凑的术语表示。
\n

\n\n

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

\n\n

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

\n