Search indexing

How can a search return results drawn from billions of pages in a fraction of a second?

Type two words, wait a quarter of a second, and get back ten results drawn from tens of billions of pages. The naive picture — the engine reads the pages and checks whether your words are in them — cannot be what happens; reading that many documents would take a datacentre days. So the work must have been done before you asked. The question is: what work, exactly, and stored in what shape?

Start by noticing what direction the naive picture runs in. It goes from document to term: take a page, look inside, see which words it holds. Ask the obvious question — what if we stored it the other way round? For each word, keep a list of every document containing it.

That is the whole trick, and it deserves a moment rather than a nod. With that structure, the query "escapement" is not a search at all. It is a lookup: find the entry for that word, read off its list. You never touch a document that does not contain the term. This is the inverted index — inverted because it reverses the natural document-to-term direction — and it is what makes retrieval fast. Almost every search system, from a web engine to the search box in your email, is built on one.

Now push on it. Two words, "escapement" and "verge", both required. What do you do? Fetch both lists, and intersect them. If the lists are kept sorted by document identifier, intersection is a single walk down both at once, advancing whichever is behind — work proportional to the length of the lists, not the size of the collection. And you can do better: walk the shorter list first, and store skip pointers so you can jump forward past long runs that cannot match.

Building the index raises its own questions. What counts as a word? Splitting on spaces sounds fine until you meet "don't", "COVID-19", or a language like Chinese that does not put spaces between words at all. That decision is tokenisation, made once at index time, and it must be made identically at query time or the lookups miss.

Then: should "running", "runs" and "ran" be the same entry? Reducing words to a common root is stemming — the Porter stemmer is the classic — and it raises recall at the cost of precision, since a stemmer that maps "university" and "universal" together has quietly merged two topics. And should "the" and "of" be indexed at all? They appear nearly everywhere, so their lists are enormous and carry almost no discriminating power. Dropping them as stop words was standard practice; modern engines usually keep them, because "to be or not to be" is a real query and phrase matching needs them.

So we can find matching documents quickly. Are we done? Here is the uncomfortable part. A common two-word query on the open web matches millions of pages. Retrieval has handed you a haystack. Nobody looks past the first ten results, so the entire value of the system now rests on a question the inverted index does not answer at all: which ten.

Ranking is a genuinely separate problem, and a harder one. The classical starting point is TF-IDF: a term matters more in a document if it appears often there (term frequency) and matters more overall if it is rare across the collection (inverse document frequency), so "escapement" carries far more weight than "the". BM25 refines this with saturation, so the fiftieth occurrence adds much less than the fifth, and with normalisation for document length. But nothing in that family knows whether a page is trustworthy, current, or actually about what it mentions. Link-based signals like PageRank added a notion of standing, and learned ranking models now combine hundreds of signals. Most large systems run a fast term-based pass to gather candidates, then expensive models to order the top few hundred.

Three refinements that connect the pieces.

The index is not a small thing sitting beside the documents; it is comparable in size to them, and its engineering is mostly compression. Document identifiers in a postings list are stored as gaps between consecutive values rather than absolute numbers, and those small gaps encode in few bits. That is not a mere optimisation — it is what lets a list stay in memory rather than on disk.

Second, a plain postings list records only that a term occurs in a document. Phrase queries and proximity ranking need to know where, so real indexes store positions alongside each entry, which costs substantially more space and is why phrase search is more expensive than term search.

Third, and honestly: the sub-second figure comes from parallelism as much as from the index. The collection is split into shards across many machines, each searching its own slice concurrently, with results merged at the end. The inverted index makes each shard's work small; sharding makes the number of shards irrelevant to the wait.

• How postings-list compression and skip pointers keep a web-scale index resident in memory.
• Why embedding-based retrieval and term-based retrieval are usually combined rather than one replacing the other.

Every term the collection defines is gathered in the glossary.