ThinkerQAQ

NOTE

2.20 倒排索引

1. 正排索引 文档Id- 文档 ，比如MySQL 1.1. 如何查找包含关键词的文档 1. 需要遍历所有文档 【O(N)】 2. 逐字逐字匹配 【O(m+n)】 2. 倒排索引 关键词- 文档Id + 文档Id- 文档 ，比如ES 先把文档分词，然后记录分词以及对应文档Id的映射，同时记录文档ID

Data Structures & Algorithms创建于 更新于 historical

这是历史学习笔记，可能存在过时或不完整的理解。

1. 正排索引

文档Id->文档，比如MySQL

1.1. 如何查找包含关键词的文档

  1. 需要遍历所有文档 【O(N)】
  2. 逐字逐字匹配 【O(m+n)】

2. 倒排索引

关键词->文档Id + 文档Id->文档，比如ES 先把文档分词，然后记录分词以及对应文档Id的映射，同时记录文档ID以及文档的映射。

2.1. 如何查找包含关键词的文档

  • 遍历分词，把匹配的取出id【O(N)】
  • 通过id取出文档【O(1)】