Term Dictionary Lookup Structures for Inverted Indexes

Every query evaluation starts with a string lookup. The user supplies a term, the engine must find that term’s entry in the dictionary, and the entry must yield the location and length of the postings list. The dictionary is small relative to the postings — typically a few percent of total index size, because vocabulary grows sublinearly in the collection while postings grow linearly — but it is consulted at least once per query term and often many times during wildcard expansion. Its access pattern is random over a modest working set, which is exactly the pattern memory hierarchies handle badly. That combination of small size, random access, and high query rate determines the design.

The dictionary entry and the posting pointer

A dictionary entry minimally holds the term, a document frequency, and a pointer to the postings. The pointer is not a machine address. Indexes are memory-mapped or read with buffered I/O, so the pointer is an offset into the postings file, and it is stable across process restarts and index copies. A 64-bit offset plus a 32-bit document frequency plus a length field is the common triple; implementations that compress postings by block also store the block-aligned offset so a reader can start decoding at a block boundary rather than at an arbitrary byte.

Document frequency is stored rather than derived because it is needed before any postings are read. Query planners use it to order a conjunction cheapest-first, and scorers use it as the input to inverse document frequency. Reading it from the entry costs one field load; deriving it from a compressed list would require decoding the whole list.

The term keys are strings over a fixed alphabet with a skewed length distribution: most terms are short, and the tail is long. Since the keys must be sorted for prefix queries and for merge-based construction, the dictionary is a sorted string table with a payload, and the question is what access structure to layer on it.

Binary search over a sorted key block

The simplest dictionary is an array of term pointers into a contiguous key blob, sorted lexicographically, with a parallel array of payloads. Lookup binary-searches the pointer array, comparing the query against each probed key, and costs O(log V) string comparisons where V is the vocabulary size.

For a vocabulary of a million terms that is about twenty comparisons. Each comparison touches two strings in different cache lines, so the real cost is dominated by cache misses rather than by character comparisons: roughly twenty dependent memory fetches, each tens of nanoseconds when it misses to main memory. Twenty dependent misses is a latency problem, not a throughput problem, and it sets a floor of several hundred nanoseconds per lookup that no amount of instruction-level cleverness removes.

The mitigation is to make comparisons cheap and to reduce their number. Storing the first four or eight bytes of each term inline with the pointer lets most comparisons be decided on a single 32-bit or 64-bit integer load, with the full string touched only when the prefixes tie. This is the same trick used by sorted string tables for on-disk key-value stores, and it typically removes over ninety percent of the string dereferences for a natural-language vocabulary, where terms sharing an eight-byte prefix are a minority.

Interpolation search replaces the halving with an estimate based on the first characters’ byte values. On a vocabulary with a roughly uniform byte distribution it converges in fewer probes than binary search, but real vocabularies cluster: many terms begin with the same few letters, and the estimate then degenerates toward a linear scan. Implementations either guard interpolation with a fallback to binary search after a probe budget, or skip it.

Hash tables and the cost of losing order

A hash table gives O(1) expected lookup: hash the term, probe a bucket, compare. For a point lookup of a known term it beats binary search by a wide margin on both instruction count and cache behaviour, because one or two cache lines are touched instead of twenty.

The loss is order. A hash table cannot answer a prefix query, cannot enumerate the vocabulary in lexicographic order, and cannot support fuzzy matching without scanning every key. Prefix queries are not an edge case in a search engine: query completion, wildcard expansion, and range filters over terms all need them. The usual compromise is a hash table as the primary lookup plus a sorted array of keys retained for enumeration, which pays both costs and is only worth it when point lookups dominate.

Open addressing with linear probing is the standard layout: a single array of entries, each holding a hash fragment, a key offset, and the payload. Storing an eight-bit or sixteen-bit hash fragment in each slot lets a probe reject most non-matching slots without touching the key, which is the same prefix-filtering idea as the inline first bytes above. Load factors near 0.7 keep probe sequences short; above that, clustering in linear probing degrades lookup time quadratically.

The hash function choice matters less than it appears, because the keys are already high-entropy strings, but the hash must be computed over the whole term or a lookup cannot be correct. A per-query sanity check on hash cost: computing a 64-bit hash over an average term of eight bytes costs a handful of multiplies, which is cheaper than a single cache miss, so hashing is not the bottleneck.

Tries and finite-state structures

A trie indexes by character position. The root has an outgoing edge per first character, each child per second character, and a term’s node holds its payload. Lookup descends one edge per character, so cost depends on term length, not vocabulary size, and a prefix query ends at a node whose subtree is exactly the set of matching terms.

A plain trie wastes memory badly: one pointer per character position times the alphabet size, or a sparse node representation with per-node allocation overhead. A radix tree (patricia trie) compresses unary paths, so a node stores a label of several characters instead of one, and the node count becomes proportional to the number of branch points rather than to total key length. This is the structure most in-memory dictionaries actually use, because it retains prefix and range queries and cuts node count by an order of magnitude relative to a character trie.

A minimal acyclic finite-state automaton goes further: it shares not only prefixes but suffixes, by merging equivalent subtrees. The result is a directed acyclic graph in which the number of states can be a small fraction of the total key length, and it still supports prefix lookup. Construction requires the keys in sorted order and a check for suffix equivalence, which is the classical incremental algorithm for minimal automata. The payload becomes the problem: because states are shared, a node can no longer own a postings pointer, so payloads must be stored in a separate array addressed by a terminal state’s index. Wildcard and edit-distance queries can be run over the automaton as a product traversal, which is where the structure earns its complexity.

Where the dictionary lives

The dictionary is usually resident in memory while the postings stay on disk or in the page cache. At a million terms with an average of ten bytes per term, the key blob is about ten megabytes, and pointers plus payloads add roughly sixteen bytes per term, so the whole dictionary occupies a few tens of megabytes. That fits in the memory of any machine running a search service, and keeping it there converts every term lookup into a memory reference rather than a disk read. The postings cannot be treated the same way: a term appearing in a tenth of ten million documents has a list of a million entries, and the union of all lists is the index.

The split creates a consistency requirement that is easy to get wrong. Dictionary offsets must be stable under concurrent index updates, so dictionary files are immutable and replaced wholesale rather than edited, and readers hold a reference to a specific dictionary version. A deleted segment leaves an entry whose postings are gone; the entry is kept until the next full rewrite, and its document frequency is what makes the planner skip it.

Front coding shrinks the dictionary by storing each term as a shared prefix length relative to its predecessor plus a suffix. It applies to any sorted representation and is described in front coding the term dictionary. The consequence for lookup is that random access disappears: a term’s key can only be reconstructed by walking back to the nearest block start, so front-coded dictionaries are block-indexed, with a fixed number of terms per block and one pointer per block.

For workloads where the vocabulary is genuinely enormous — identifiers, URLs, product codes — the sorted block with inline prefix bytes remains the default, because it is the only structure whose construction is a sort and whose failure modes are all understood. Tries win when prefix enumeration is the primary access pattern rather than a sideline, and delta encoding and variable-byte postings is what makes the postings behind those pointers small enough that the pointer itself is a meaningful fraction of the entry.