How can a search engine find one word among billions of pages in a blink?

A search engine answers quickly because it does not read the web when you search. It reads it beforehand, and writes down, for every word, a list of the pages where that word appears. When you type a word, it simply opens that word's list. This is called an inverted index, and it is the most popular data structure in document retrieval systems.

Think of the index at the back of a textbook. You don't reread the whole book to find where "volcano" is mentioned; you look up the word and get page numbers. A search engine does the same with pages of the web instead of pages of a book. Without an index it would have to scan every document for every question: an index of 10,000 documents can be queried within milliseconds, while a scan of every word in 10,000 large documents could take hours.

The trick is in the name. First, the engine makes a forward index, which stores a list of words for each document. Then it flips this around into an inverted index, which lists the documents for each word. A tiny made-up example: if page 1 says "cats purr", page 2 says "dogs bark" and page 3 says "cats and dogs", the entry for "cats" says pages 1 and 3.

People were doing this long before computers. In pre-computer times, concordances to important books were assembled by hand, and they were effectively inverted indexes. A computer simply does the same job on a vast scale, and without tiring.