What is an inverted index and what data structures are used?

Inverted index is a data structure widely used in search engines for fast document retrieval based on keywords. It stores a mapping from words (terms) to the list of documents where these words appear.

Main components:

• Vocabulary: a set of unique words from all documents.
• Posting lists: for each word, a list of documents (often with positions of the word in the document).

Typical data structures:

• Hash tables or trees (e.g., B-trees) for the vocabulary.
• Linked lists or arrays for posting lists.

Example:

word: "python"
posting list: [doc1: positions [3, 15], doc5: positions [7]]

This allows efficient queries like "find all documents containing 'python'" or more complex multi-word queries.

The inverted index is fundamental for full-text search and document ranking systems.