The 30 second answer
A finite-state transducer is a compact automaton that maps keys to outputs. It shares common prefixes and suffixes, so a large sorted set of terms fits in little memory. Lucene's BlockTree terms dictionary groups terms into blocks by shared prefix and keeps that prefix trie in memory as an FST, which points to the right block on disk.
What it is. A finite-state automaton recognises a set of strings; a transducer also emits an output along the path, for example a file pointer. A minimal FST merges shared prefixes, like a trie, and shared suffixes too, which a trie cannot. The Lucene util.fst package documents fast, low-memory construction of the minimal FST, with the restriction that inputs must be added in sorted order, plus a compact byte[] representation and iterators that behave like a sorted map.
How the terms dictionary uses it. The Lucene BlockTree terms dictionary "organizes all terms into blocks according to shared prefix, such that each block has enough terms, and then stores the prefix trie in memory as an FST as the index structure." A term lookup walks the FST to find the block, then reads that block from the .tim file. The full term list stays on disk; only the small prefix index sits on the heap.
Why this fits Lucene. Segments are written once and never modified, so the sorted-input requirement costs nothing: the segment's terms are already sorted when it is written. Because the structure is ordered, it also supports prefix enumeration, which helps prefix and wildcard queries, and the same machinery backs completion suggesters.
Comparisons.
- Hash table: fast exact lookup, but no order and no prefix search.
- B-tree: ordered and good for updates in place on disk, but larger, and Lucene never updates a segment in place.
- Trie: prefix search, but one node per character costs far more memory. See tries and autocomplete.