Why is a search engine's term dictionary kept in sorted order rather than as a hash table?

## What the term dictionary is The inverted index has two halves. The postings hold the documents; the term dictionary is the lookup layer that gets you to the right postings list. Each entry is roughly: the term itself, its document frequency, the total number of occurrences (in engines that track it), and a pointer — a file offset — to where the postings and the positional data begin. Its size is driven by the number of *distinct* terms, which is why high-cardinality fields, n-gram fields, identifiers and misspellings inflate it. ## Why not a hash table? A hash table is the obvious structure if the only operation is "find the postings for exactly this term". Real search issues several other operations against the dictionary, and every one of them requires that terms with a common prefix or a common range live next to each other: - **Prefix and autocomplete queries** enumerate all terms starting with a string. - **Wildcard and regular-expression queries** enumerate candidate terms; when the pattern has a literal prefix, sorted order lets the engine seek straight to that region instead of scanning all terms. - **Range queries** on lexically or numerically ordered terms walk an interval. - **Fuzzy queries** enumerate terms within an edit distance, which implementations drive as a guided walk of the sorted term space rather than a comparison against every term. - **Iterating all terms of a field**, which faceting-style features and index introspection need. Under hashing, every one of these degrades to a full scan of the term space in random order. ## Sorting enables compression Sorted terms are highly redundant: `search`, `searcher`, `searches`, `searching` share six characters. Front-coding (prefix compression) stores the shared prefix length plus the differing suffix, which shrinks the dictionary substantially for natural-language vocabularies. Some engines go further and represent the dictionary as a finite-state structure that shares both prefixes and suffixes, compressing the term space harder still while remaining ordered and traversable. None of this is available to a hash table, which deliberately destroys locality. ## Sorting bounds the memory A large corpus can have hundreds of millions of distinct terms; holding all of them in RAM is often not affordable. The standard layout is: write terms in sorted order into fixed-size blocks on disk, and keep in memory a *sparse index* holding only every Nth term with the offset of its block. A lookup binary-searches the sparse index in RAM to find the one candidate block, reads that single block, and scans it linearly. Memory cost is divided by N, and the disk cost is one seek. That whole design depends on the on-disk terms being ordered. ## Sorting makes merging cheap Search engines build index units incrementally and merge them in the background. Merging two dictionaries that are each sorted is a single linear pass — advance whichever side has the smaller term, and when both sides carry the same term, concatenate or merge their postings. Merging two hash tables requires rehashing everything. Since merging is a continuous background cost on every write-heavy index, this property matters more than it first appears. ## What sorting costs Exact lookup is O(log n) block search plus a block scan, not O(1). In practice the constant factors go the other way — the block containing a hot term is likely already in the page cache, and a hash lookup on a disk-resident table would be a random seek — but you should state the trade-off honestly rather than pretend sorting is free. Some engines additionally put a Bloom-filter-style structure in front of the dictionary specifically to reject terms that do not exist without paying the block read, which is a good example of using hashing *beside* the sorted dictionary rather than instead of it. ## How to answer this in an interview Lead with the capability argument — prefix, wildcard, range and fuzzy queries are dictionary enumerations and need order. Then add the two systems arguments: prefix compression, and a sparse in-memory index over ordered on-disk blocks that keeps RAM bounded. Close with merging. If you only say "so you can do prefix search", you have given a correct but shallow answer; the memory and merge arguments are what make it a design decision rather than a feature.