倒排索引Inverted Index倒排索引Inverted Index一、先从正排索引说起二、什么是倒排索引三、两者对比四、倒排索引的组成1. 词项字典Term Dictionary2. 倒排列表Posting List五、构建过程第一步文档分词第二步建立词到文档的映射第三步记录附加信息增强版六、查询过程七、与 BM25 的关系八、在向量数据库中的应用九、优缺点优点缺点十、典型应用场景总结倒排索引Inverted Index一、先从正排索引说起要理解倒排索引先看正排索引是什么。正排索引Forward Index是我们最自然的思考方式从文档出发找出文档里包含哪些词。文档ID → 内容 → 提取所有词举个例子假设有三篇文章文档ID内容Doc1“苹果手机很好用”Doc2“我喜欢吃苹果”Doc3“手机拍照功能强大”正排索引就是按文档整理出词汇表文档ID包含的词汇Doc1苹果、手机、很好用Doc2我、喜欢、吃、苹果Doc3手机、拍照、功能、强大这种结构存数据没问题但搜索的时候很慢。比如用户搜“苹果”需要遍历所有文档逐个检查是否包含这个词。文档少还好如果有几百万篇文章每次都全表扫描效率极低。二、什么是倒排索引倒排索引Inverted Index的思路正好反过来从词出发记录这个词出现在哪些文档里。把上面的数据倒过来词汇出现位置苹果Doc1, Doc2手机Doc1, Doc3很好用Doc1我Doc2喜欢Doc2吃Doc2拍照Doc3功能Doc3强大Doc3这就是倒排索引。用户搜“苹果”直接从倒排索引里找到这个词对应的文档列表瞬间返回结果。三、两者对比对比项正排索引倒排索引数据结构文档 → 词汇词汇 → 文档列表查询过程遍历所有文档直接查词表查询速度慢O(n)快O(1)存储结构简单稍复杂更新成本低较高典型应用数据库行存储搜索引擎、全文检索打个比方正排索引 一本书前面的目录按章节找内容倒排索引 一本书后面的关键词索引按词找位置四、倒排索引的组成倒排索引由两部分组成1. 词项字典Term Dictionary按字母顺序排列的所有词每个词指向它的倒排列表。苹果 → [Doc1, Doc2] 手机 → [Doc1, Doc3] 拍照 → [Doc3] ...2. 倒排列表Posting List每个词对应的文档列表通常会存储存储内容作用文档ID标识文档词频TF计算相关性位置信息支持短语搜索偏移量支持高亮存储的越详细查询功能越丰富但存储空间也越大。五、构建过程第一步文档分词原始文档Doc1: “苹果手机好用”Doc2: “我喜欢吃苹果”分词后Doc1: [“苹果”, “手机”, “好用”]Doc2: [“我”, “喜欢”, “吃”, “苹果”]第二步建立词到文档的映射词文档列表苹果[Doc1, Doc2]手机[Doc1]好用[Doc1]我[Doc2]喜欢[Doc2]吃[Doc2]第三步记录附加信息增强版词(文档, 词频, 位置)苹果(Doc1, 1, 0), (Doc2, 1, 3)手机(Doc1, 1, 1)好用(Doc1, 1, 2)我(Doc2, 1, 0)喜欢(Doc2, 1, 1)吃(Doc2, 1, 2)有了位置信息就能支持“苹果手机”这种短语搜索因为可以判断“苹果”和“手机”在Doc1中相邻出现。六、查询过程用户搜索“苹果手机”分词[“苹果”, “手机”]查倒排索引苹果 → [Doc1, Doc2]手机 → [Doc1, Doc3]求交集AND两个词都出现的文档 → [Doc1]返回结果Doc1如果是 OR 查询则合并列表 → [Doc1, Doc2, Doc3]七、与 BM25 的关系BM25 是计算搜索结果相关性的算法它的核心就是基于倒排索引。score(D, Q) Σ IDF(q) × (TF × (k₁1)) / (TF k₁ × (1 - b b × |D|/avgDL))用到的数据都来自倒排索引TF词频倒排列表里存着IDF逆文档频率根据词在多少个文档中出现计算所以倒排索引是搜索引擎的基础BM25 是排名的算法。八、在向量数据库中的应用像 Milvus 支持稀疏向量底层用的就是倒排索引的思路# 稀疏向量本质上就是 {词: 权重} 的倒排格式sparse_vector{苹果:0.8,手机:0.6}# 查询时也是用倒排索引快速定位collection.search(data[{苹果:0.7,手机:0.5}])稠密向量BERT、BGE做语义搜索倒排索引BM25、SPLADE做关键词匹配两者经常结合使用。九、优缺点优点查询速度快O(1) 级别支持布尔查询AND/OR/NOT可扩展性强适合海量数据缺点构建需要时间更新成本高存储空间比原文本大需要存索引无法处理同义词、语义匹配这一点靠稠密向量补救十、典型应用场景场景说明搜索引擎Google、百度最核心的数据结构数据库全文检索MySQL FULLTEXT、Elasticsearch推荐系统用户标签反向索引向量数据库稀疏向量检索总结倒排索引的核心思想就一句话不查文档找词而是查词找文档。这种反向的思路让全文搜索从全表扫描变成了查字典速度提升了成百上千倍。无论是 Google 搜索、数据库索引还是向量检索背后都离不开倒排索引。
倒排索引Inverted Index倒排索引Inverted Index一、先从正排索引说起二、什么是倒排索引三、两者对比四、倒排索引的组成1. 词项字典Term Dictionary2. 倒排列表Posting List五、构建过程第一步文档分词第二步建立词到文档的映射第三步记录附加信息增强版六、查询过程七、与 BM25 的关系八、在向量数据库中的应用九、优缺点优点缺点十、典型应用场景总结倒排索引Inverted Index一、先从正排索引说起要理解倒排索引先看正排索引是什么。正排索引Forward Index是我们最自然的思考方式从文档出发找出文档里包含哪些词。文档ID → 内容 → 提取所有词举个例子假设有三篇文章文档ID内容Doc1“苹果手机很好用”Doc2“我喜欢吃苹果”Doc3“手机拍照功能强大”正排索引就是按文档整理出词汇表文档ID包含的词汇Doc1苹果、手机、很好用Doc2我、喜欢、吃、苹果Doc3手机、拍照、功能、强大这种结构存数据没问题但搜索的时候很慢。比如用户搜“苹果”需要遍历所有文档逐个检查是否包含这个词。文档少还好如果有几百万篇文章每次都全表扫描效率极低。二、什么是倒排索引倒排索引Inverted Index的思路正好反过来从词出发记录这个词出现在哪些文档里。把上面的数据倒过来词汇出现位置苹果Doc1, Doc2手机Doc1, Doc3很好用Doc1我Doc2喜欢Doc2吃Doc2拍照Doc3功能Doc3强大Doc3这就是倒排索引。用户搜“苹果”直接从倒排索引里找到这个词对应的文档列表瞬间返回结果。三、两者对比对比项正排索引倒排索引数据结构文档 → 词汇词汇 → 文档列表查询过程遍历所有文档直接查词表查询速度慢O(n)快O(1)存储结构简单稍复杂更新成本低较高典型应用数据库行存储搜索引擎、全文检索打个比方正排索引 一本书前面的目录按章节找内容倒排索引 一本书后面的关键词索引按词找位置四、倒排索引的组成倒排索引由两部分组成1. 词项字典Term Dictionary按字母顺序排列的所有词每个词指向它的倒排列表。苹果 → [Doc1, Doc2] 手机 → [Doc1, Doc3] 拍照 → [Doc3] ...2. 倒排列表Posting List每个词对应的文档列表通常会存储存储内容作用文档ID标识文档词频TF计算相关性位置信息支持短语搜索偏移量支持高亮存储的越详细查询功能越丰富但存储空间也越大。五、构建过程第一步文档分词原始文档Doc1: “苹果手机好用”Doc2: “我喜欢吃苹果”分词后Doc1: [“苹果”, “手机”, “好用”]Doc2: [“我”, “喜欢”, “吃”, “苹果”]第二步建立词到文档的映射词文档列表苹果[Doc1, Doc2]手机[Doc1]好用[Doc1]我[Doc2]喜欢[Doc2]吃[Doc2]第三步记录附加信息增强版词(文档, 词频, 位置)苹果(Doc1, 1, 0), (Doc2, 1, 3)手机(Doc1, 1, 1)好用(Doc1, 1, 2)我(Doc2, 1, 0)喜欢(Doc2, 1, 1)吃(Doc2, 1, 2)有了位置信息就能支持“苹果手机”这种短语搜索因为可以判断“苹果”和“手机”在Doc1中相邻出现。六、查询过程用户搜索“苹果手机”分词[“苹果”, “手机”]查倒排索引苹果 → [Doc1, Doc2]手机 → [Doc1, Doc3]求交集AND两个词都出现的文档 → [Doc1]返回结果Doc1如果是 OR 查询则合并列表 → [Doc1, Doc2, Doc3]七、与 BM25 的关系BM25 是计算搜索结果相关性的算法它的核心就是基于倒排索引。score(D, Q) Σ IDF(q) × (TF × (k₁1)) / (TF k₁ × (1 - b b × |D|/avgDL))用到的数据都来自倒排索引TF词频倒排列表里存着IDF逆文档频率根据词在多少个文档中出现计算所以倒排索引是搜索引擎的基础BM25 是排名的算法。八、在向量数据库中的应用像 Milvus 支持稀疏向量底层用的就是倒排索引的思路# 稀疏向量本质上就是 {词: 权重} 的倒排格式sparse_vector{苹果:0.8,手机:0.6}# 查询时也是用倒排索引快速定位collection.search(data[{苹果:0.7,手机:0.5}])稠密向量BERT、BGE做语义搜索倒排索引BM25、SPLADE做关键词匹配两者经常结合使用。九、优缺点优点查询速度快O(1) 级别支持布尔查询AND/OR/NOT可扩展性强适合海量数据缺点构建需要时间更新成本高存储空间比原文本大需要存索引无法处理同义词、语义匹配这一点靠稠密向量补救十、典型应用场景场景说明搜索引擎Google、百度最核心的数据结构数据库全文检索MySQL FULLTEXT、Elasticsearch推荐系统用户标签反向索引向量数据库稀疏向量检索总结倒排索引的核心思想就一句话不查文档找词而是查词找文档。这种反向的思路让全文搜索从全表扫描变成了查字典速度提升了成百上千倍。无论是 Google 搜索、数据库索引还是向量检索背后都离不开倒排索引。
