Inverted index

In short: An inverted index maps each word to the list of documents in which it occurs. It makes full-text search fast.

In more detail: Instead of scanning all texts for every search, you look the word up in the index, like the index at the back of a book.

In Depth

• Structure: word → [document ID, ...], often with frequency and positions (for phrase search such as “red cat”).
• Preprocessing: Lower-casing, splitting into words (tokenisation), word stems (stemming), dropping stop words.
• Several words: The lists are intersected (AND) or merged (OR). Because they are sorted, merging is very fast.
• Ranking: Methods like TF-IDF and BM25 weight rare words higher. See hybrid search.
• Use: Lucene, Elasticsearch, PostgreSQL full text (GIN index), search engines, the wiki search box.
• Cost: The index takes space and must be updated on changes.

See also: Elasticsearch