[LUCENE-2948] Make var gap terms index a partial prefix trie

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Won't Fix
• Fix Version/s: 4.0-ALPHA
• Component/s: core/index
• Lucene Fields: New
• Assignee: Michael McCandless
• Reporter: Michael McCandless
• Created: 03/Mar/11 16:50
• Updated: 28/Aug/22 12:42
• Resolved: 20/Mar/12 15:19

Description

Var gap stores (in an FST) the indexed terms (every 32nd term, by
default), minus their non-distinguishing suffixes.

However, often times the resulting FST is "close" to a prefix trie in
some portion of the terms space.

By allowing some nodes of the FST to store all outgoing edges,
including ones that do not lead to an indexed term, and by recording
that this node is then "authoritative" as to what terms exist in the
terms dict from that prefix, we can get some important benefits:

• It becomes possible to know that a certain term prefix cannot
  exist in the terms index, which means we can save a disk seek in
  some cases (like PK lookup, docFreq, etc.)

• We can query for the next possible prefix in the index, allowing
  some MTQs (eg FuzzyQuery) to save disk seeks.

Basically, the terms index is able to answer questions that previously
required seeking/scanning in the terms dict file.