The Inverted Index

The fundamental data structure: a map from term -> documents containing it.

Documents:
  doc1: "the cat sat on the mat"
  doc2: "the dog lay on the rug"
  doc3: "cat and dog ran fast"

After tokenization (with stopwords removed):
  doc1: [cat, sat, mat]
  doc2: [dog, lay, rug]
  doc3: [cat, dog, ran, fast]

Inverted index:
  cat  -> {doc1, doc3}
  sat  -> {doc1}
  mat  -> {doc1}
  dog  -> {doc2, doc3}
  lay  -> {doc2}
  rug  -> {doc2}
  ran  -> {doc3}
  fast -> {doc3}

For a query like cat AND dog, look up both posting lists and intersect:

• cat -> {1, 3}
• dog -> {2, 3}
• Intersection: {3}

That's how Google, Elasticsearch, Lucene all work — at scale, with lots of cleverness for compression and skip lists, but the core is this map.

For this lesson: build the index from a list of docs.