2.20 Inverted Index

1. Forward Index

documentId -> document, such as MySQL

1.1. How to Find Documents Containing a Keyword

1. Traverse all documents 【O(N)】
2. Match character by character 【O(m+n)】

2. Inverted Index

keyword -> documentId + documentId -> document, such as ES First tokenize the document, then record the mapping between tokens and document IDs, and also record the mapping between document IDs and documents.

2.1. How to Find Documents Containing a Keyword

• Traverse the tokens and retrieve the matching IDs 【O(N)】
• Retrieve the document by ID 【O(1)】