Inverted index.

also: inverted indexes · inverted indices · posting list · posting lists

A map from each term to the list of documents containing it, so a search looks up words instead of scanning every document.

the two-minute refresher

A forward index maps document → words; an inverted index maps word → documents.
SQL LIKE '%red%' scans every row and matches characters ('bored' contains 'red').
Query 'running shoes': look up each term's posting list and intersect: microseconds.
Built at index time, so writes cost more and reads are fast.

also: inverted indexes · inverted indices · posting list · posting lists

A map from each term to the list of documents containing it, so a search looks up words instead of scanning every document.

A forward index maps document → words; an inverted index maps word → documents.
SQL LIKE '%red%' scans every row and matches characters ('bored' contains 'red').
Query 'running shoes': look up each term's posting list and intersect: microseconds.
Built at index time, so writes cost more and reads are fast.