在我的 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“新手”，我想了解以下内容：

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

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

Theory

有一个博客文章 http://blog.mikemccandless.com/2014/05/choosing-fast-unique-identifier-uuid.html关于 Lucene 术语索引和查找性能。它清楚地揭示了通过 id 查找文档的复杂性的所有细节。这篇文章很旧了，但自那以后没有任何改变。

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

• Lucene 是一个搜索引擎，其中检索的最小元素是文本术语，因此这意味着：二进制、数字和字符串字段在BlockTree 术语词典 http://lucene.apache.org/core/4_8_0/core/org/apache/lucene/codecs/BlockTreeTermsWriter.html.
• In general, the complexity of lookup depends on the term length: Lucene uses an in-memory prefix-trie index structure to perform a term lookup. Due to restrictions of real-world hardware and software implementations (in order to avoid superfluous disk reads and memory overflow for extremely large tries), Lucene uses a BlockTree structure. This means it stores prefix-trie in small chunks on disk and loads only one chunk at time. This is why it's so important to generate keys in an easy-to-read order. So let's arrange the factors according to the degree of their influence:
  • 术语的长度 - 要加载更多块
  • term 的模式 - 避免多余的读取
  • 术语计数 - 减少块计数

算法和复杂性

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

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

Here is an example of DAFSA for 3 terms: bath, bat and batch:

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