Inverted indexes
How text search finds the documents that contain a word, without reading the documents.
5 minute lesson
From words to documents
A normal index is sorted from the start of a value, so it cannot find a word in the middle of a text. A search for "index" in a million articles would read them all. An inverted index turns the data round: for every word it keeps the list of documents that contain it.
- databasedocuments 1, 4, 9
- indexdocuments 4, 7
- replicadocuments 2, 9
- inverted index
- An index from each word to the list of documents that contain it.
Key terms
Searching for two words
- Look up
The query is "database index". Each word is looked up, which is one fast step per word.
- database1, 4, 9
- index4, 7
- Combine
For documents with both words, the two lists are intersected. Only document 4 is on both.
- Both listsintersect
- Resultdocument 4
- Rank
With many matches the engine sorts them, for instance by how often the words occur in each. No document was read to find the matches.
- Matchesranked
- Shownbest first
An inverted index holds: cache in documents 2, 5, 8 and 11; latency in documents 3, 5, 9 and 11. A query asks for documents that contain both words.
Which documents match?
- 5 and 11
- 2 and 3
- 8 and 9
- All eight
Show the answer
- 5 and 11
A document with both words must be on both lists. Only 5 and 11 are. The engine found that by comparing two short lists of numbers, without opening a single document. A query for either word would take the union of the lists instead.
Both words: intersect the two lists. Either word: unite them.
Words have to be made comparable
Before text goes into the index, it is broken up and tidied: split into words, put in lower case, and often reduced to a word's stem. The query goes through exactly the same steps. That is why a search for "Running" finds a text that says "runs".
- TextThe Indexes
- Split and lowerthe, indexes
- Stemindex
An article contains the word "Databases". A search for "database" does not find it. The index stores words exactly as they appear in the text.
What is missing?
- The same tidying of words for texts and queries
- A second index that is sorted by article length
- A larger server for the search engine to run on
- A rule that users must type words as written
Show the answer
- The same tidying of words for texts and queries
To the index, "Databases" and "database" are two different strings, so the lookup finds nothing. If both the article and the query are put in lower case and reduced to the stem, both become the same term, and the search matches. What matters is that the two sides are treated identically.
An index matches terms exactly. Process documents and queries the same way so that they meet.
Where inverted indexes live
- In a search engine, a separate system built around them, with ranking and typo tolerance.
- In the database itself. PostgreSQL, for instance, has an index type for text and arrays that stores each word with the rows that contain it.
How does an inverted index answer a search for two words?
Show the answer
It stores, for every word, the list of documents that contain it. Each word of the query is looked up, and the two lists are intersected: documents on both lists contain both words. The matches are then ranked. The documents themselves are not read to find them.
Recap
- An inverted index maps each word to the documents that contain it.
- Text and queries go through the same processing: split, lower case, stems.
- It lives in a search engine or in the database. A search engine holds a copy, not the truth.