The Inverted Index

Terms point to documents

A database index maps a row to its values; an inverted index maps each term to the list of documents that contain it (a postings list, optionally with positions and frequencies). At index time, text is analysed into terms (for example lower-cased words). At search time, the query text is analysed the same way and Elasticsearch looks up each term, intersects or unions the postings lists and scores the matching documents. Lucene writes the index in immutable segments that are merged in the background; updates and deletes are recorded as new versions plus deletion markers rather than in-place edits. Structured fields (numbers, dates, keywords) also use doc values, a column-oriented store used for sorting and aggregations.

Building an inverted index by hand

Three tiny documents after lower-casing and splitting on words.

doc 1: "Red running shoe"
doc 2: "Blue running jacket"
doc 3: "Red jacket"

term      -> postings (doc ids)
blue      -> [2]
jacket    -> [2, 3]
red       -> [1, 3]
running   -> [1, 2]
shoe      -> [1]

query "red jacket" -> terms [red, jacket]
  OR  -> docs 1, 2, 3 (doc 3 matches both, so it scores highest)
  AND -> doc 3 only

The index at the back of a book

A book index lists each word with the pages where it appears, so you jump straight to page 212 instead of reading every page. An inverted index does the same for documents.

Quick check: What does an inverted index map?

• Each term to the documents that contain it
• Each document to its storage address only
• Each shard to a node
• Each user to their permissions