Inverted Index
Subject: Computer and Technology noun /ɪnˈvɜːr.tɪd ˈɪn.dɛks/ 1 definition
- information-retrieval
- data-structures
- search-engines
- full-text-search
-
Definition (noun)
Entry #233 · UpdatedAn Inverted Index is a fundamental data structure in information retrieval and database engines that maps unique keys—typically normalized terms, tokens, or field values—to lists of identifiers for the documents or records containing them. Instead of scanning every document as a forward index does when searching for a keyword, it reverses the mapping by storing a dictionary of keys linked to postings lists of matching document IDs, often paired with term frequencies or positional offsets. This organization delivers fast Boolean, phrase, and ranked full-text queries across large corpora, trading higher write-time indexing overhead and storage footprint for rapid read-time lookup.
Common Forms
Record-Level Inverted Index: Maps each term solely to a list of containing document or record IDs, keeping storage compact for Boolean filtering and membership lookups.
Word-Level Inverted Index: Supplements document IDs in each postings list with the exact word or byte positions of every occurrence, enabling phrase matching, proximity queries, and snippet highlighting.
N-Gram Inverted Index: Tokenizes text into overlapping character sequences (such as trigrams) before indexing, supporting fast wildcard, substring, and typo-tolerant searches at the expense of larger postings lists.
Segmented Immutable Inverted Index: Writes updates into separate immutable index segments that merge asynchronously in the background (as in Apache Lucene), avoiding costly in-place edits to sorted postings lists.
Example
In an e-commerce search engine, an inverted index maps
"ceramic"to postings list[104, 289, 512]and"mug"to[42, 104, 512, 900]. When a shopper searches forceramic AND mug, the engine intersects those two sorted lists in memory to return products104and512immediately without scanning the full product catalog.