The arrow has work inside it

The inverted index from the previous chapter contained rows like these:

It is tempting to compress each row into an arrow:

fox → [1, 2]

But an arrow is notation, not an operation. Before reading [1, 2], the query engine must locate fox among all dictionary terms. A miss must stop at the right place. A prefix such as fi must find field without scanning unrelated terms. A capped completion must decide which five terms count as the first five.

The index therefore contains another index.

Before choosing a representation, name the questions. A useful static lexicon interface has four:

1. EXACT(x) — return the payload for $x$, or report absence;
2. LOWER-BOUND(x) — return the first term not less than $x$;
3. PREFIX-SPAN(p) — return the half-open interval containing every term that begins with $p$;
4. ENUMERATE(span, k, order) — return at most $k$ terms in the promised semantic order.

Exact lookup alone does not imply the other three. A hash table can answer the first without preserving any useful neighborhood. A sorted sequence answers the first three, but its lexical order may not be the authored or popularity order promised by a completion surface.

Start with the reference answer

A sequential scan is a poor default for a large lexicon and an excellent oracle. It states exact membership and source-order enumeration without hiding either behind a layout.

SEQUENTIAL-EXACT(L, key)
Input:  finite lexicon L[1:n] in source order, query key
Output: the payload paired with key, or NIL

for each entry e in L
    if e.term = key
        return e.payload
return NIL

The loop performs at most $n$ equality tests and uses $O(1)$ extra space. More importantly, every faster implementation can be checked against it:

$$\operatorname{FastExact}(L,x) = \operatorname{SequentialExact}(L,x).$$

For capped prefixes, the reference law is equally plain. Filter the source sequence by the prefix, then take the first $k$. The cap comes last:

$$\operatorname{Cap}_k(\operatorname{FilterPrefix}_p(L)).$$

This order matters. Sorting matching terms first and then taking $k$ answers a different question whenever source order and lexical order differ.

Comparison search earns a logarithm

Sort $n$ distinct terms. An exact comparison search repeatedly asks whether the query lies before, at, or after a chosen term. For a successful lookup, there are $n$ possible answers. If absence must also identify one of the $n+1$ gaps, there are at least $2n+1$ outcomes across hits and misses.

A binary decision tree of height $h$ has at most $2^h$ leaves. Distinguishing $n+1$ insertion gaps therefore requires

$$2^h \ge n+1,$$

so

$$h \ge \lceil \log_2(n+1) \rceil.$$

Binary search meets that envelope up to the exact convention used for hits and gaps. Its worst-case comparison count is logarithmic, its storage is the flat sorted sequence itself, and a prefix span is two boundary searches followed by the number of results actually returned.

The model qualification is the lesson. A bytewise radix trie does not ask whether one whole string is less than another. It consumes key units and branches by their values. A hash table projects the key into a bucket. Neither contradicts the comparison lower bound because neither is confined to comparison decisions.

Six structures, four questions

The representations below are siblings, not a ladder from primitive to advanced.

Here $|x|$ is the length of the query key and $r$ is the number of enumerated results. The table deliberately does not crown a winner. It also leaves out constants that often decide the measurement: cache lines, pointer chasing, branch prediction, decoded bytes, and allocation.

HASH-EXACT(H, key)
Input:  hash table H whose buckets retain original terms, query key
Output: the payload paired with key, or NIL

b ← H.BUCKET(HASH(key))
for each entry e in b
    if e.term = key
        return e.payload
return NIL

One lexicon, several physical views

Suppose exact membership is frequent, prefix lookup is frequent, and capped results must remain in authored order. Hash order cannot serve prefix lookup. Lexical order cannot by itself recover authored order after a cap.

The honest representation is often one term store plus small views:

• a lexical permutation for boundary searches;
• a source-order ordinal for capped enumeration;
• optionally a hash projection for exact lookup;
• payload offsets shared by every view.

An ordinal permutation over $n$ entries requires at least enough bits to name one of $n$ positions per entry, or approximately

$$n\lceil\log_2 n\rceil \text{ bits}$$

before compression and headers. That is not free, but it is usually cheaper and safer than duplicating the term bytes. It also exposes a useful invariant: every view resolves to the same canonical term identity.

Three cost models, not one winner

Asymptotic comparisons answer one question. A production choice needs at least three ledgers:

1. abstract work — comparisons, probes, transitions, decoded key units;
2. machine work — cache lines, branches, pointer dependencies, allocation;
3. movement — bytes transferred from storage or network and bytes retained.

A flat sorted array can lose in comparison count and win in elapsed time while it fits in cache. A compact automaton can win in resident bytes and lose construction time. A hash table can win exact hits and make prefix enumeration impossible without another view. These are not contradictory benchmark results. They are different observations.

The workload needs strata too: successful exact hits, exact misses, narrow prefixes, absent prefixes, prefixes exceeding the cap, and deliberately forced hash collisions. Reporting only the average lets common easy hits conceal a broken or expensive miss path.

The lineage is wider than one tree

Where each structure is wrong

• A sequential sequence is right for a tiny, cold, rarely queried vocabulary.
• A sorted sequence is hard to beat when it is static and cache-resident.
• A hash-only dictionary is wrong when prefix or ordered range questions are part of the interface.
• A pointer-heavy trie is wrong when its node overhead dominates its strings.
• Front coding is wrong when frequent random hits repeatedly decode long blocks.
• A minimal automaton is wrong when updates are frequent or payload order is the primary contract.

The rule is not “benchmark everything forever.” First remove structures that cannot answer the required questions. Then compare the surviving structures in the workload and memory level that will actually use them.

Lessons

• The term-to-postings arrow contains a second search problem: locating and enumerating terms in the lexicon.
• Exact lookup, lower bound, prefix span, and capped ordered enumeration are distinct operations.
• Comparison lookup needs logarithmic height in the worst case; hashing and digital tries use stronger operations and belong to different models.
• A hash locates candidates. Exact equality establishes identity.
• A cap observes enumeration order. Reordering before capping changes results.
• One canonical term store can support several small physical views when one order cannot answer every question.
• Choose among representations only after naming abstract work, machine work, movement, and workload strata.

Practice

The dictionary can agree and still be wrong

The lexicon can now locate café exactly and enumerate every ca prefix in the promised order. But the document builder may have stored a composed é while the query arrives as e followed by a combining mark. Or one side may split camelCase while the other preserves it.

The next chapter makes that disagreement explicit. A lookup is meaningful only after indexing and querying share the same analyzer, ordering, and field provenance contract.

References

1. Knuth. “Structured Programming with go to Statements.” ACM Computing Surveys, 1974. — primary source for the epigraph and its warning about optimizing before identifying the consequential work
2. Fredkin. “Trie Memory.” Communications of the ACM, 1960. — early digital-search structure and the trie name
3. Morrison. “PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric.” Journal of the ACM, 1968. — compressed digital paths for information retrieval
4. Carter and Wegman. “Universal Classes of Hash Functions.” Journal of Computer and System Sciences, 1979. — expected hashing guarantees independent of the input sequence
5. Manning, Raghavan, Schütze. “Dictionary Data Structures.” Introduction to Information Retrieval, 2008. — search-engine dictionary representations and term lookup