目录
1.基本思想
倒排索引（Inverted Index） 是全文检索和搜索引擎中最核心的数据结构之一。它把“文档 → 包含的词”反过来组织成“词 → 包含该词的文档列表”，因此称为“倒排”。
正向索引（正排）
文档1 -> [苹果, 手机, 发布]
文档2 -> [苹果, 电脑, 发布]
文档3 -> [华为, 手机]
正排：按文档 ID，保存文档包含哪些词。
搜索 “苹果”，需要遍历全部文档，逐个检查是否包含，海量数据很慢。
倒排索引
把关系反转：词条 -> 包含该词的文档列表（倒排记录表，Posting List）
苹果 -> [文档1, 文档2]
手机 -> [文档1, 文档3]
发布 -> [文档1, 文档2]
电脑 -> [文档2]
华为 -> [文档3]查询“苹果 手机”时，只需取出“苹果”和“手机”的文档列表求交集，就能快速找到同时包含两个词的文档。
2.典型结构
倒排索引通常由两部分组成：
1.词典（Term Dictionary）
苹果
手机
发布
电脑
华为所有单词 / 词条，记录词条本身 + 指向倒排记录表的指针，一般会加索引（哈希表、B+树、FST、Trie 等结构组织）快速查找 term。
2.倒排记录表（Posting List， postings）
每个 term 对应的文档 ID 列表，还可附加信息：
- doc_id：文档编号
- tf（term frequency）：词在该文档出现次数（用于相关性打分，如 BM25）
- position：词在文档内的位置（用于短语检索、高亮）
- offset：字符偏移
3.构建流程
典型构建过程：
-
文档采集：获取网页、文章、数据库记录等。
-
分词：中文分词、英文按空格/词干处理。
-
归一化：转小写、去标点、词干还原、同义词处理等。
-
去停用词：可选，如“的”“是”“the”等。
-
生成词项-文档映射：统计每个词出现在哪些文档、出现次数、位置。
-
排序与压缩：按 docID 排序，使用 delta 编码、Varint、Roaring Bitmap 等压缩倒排列表。
-
写入索引文件：形成可持久化、可查询的索引。
4.查询方式
倒排索引支持多种查询：
-
单词查询：查“苹果”直接取倒排列表。
-
布尔查询：
苹果 AND 手机对列表求交集；苹果 OR 华为求并集。 -
短语查询：利用 positions 判断词是否相邻。
-
前缀/通配查询：借助 Trie、FST 等词典结构。
-
相关性排序：结合 TF-IDF、BM25 等计算得分。
如：
苹果 -> [1, 2]
手机 -> [1, 3]苹果 AND 手机 的交集是 [1]，即文档1。
5.优化手段
- 跳表（Skip List）：长 posting list 增加跳跃指针，合并时跳过大量不匹配 doc，加速求交
- 文档编号压缩：不存完整 docId，存差值（delta 编码），节省磁盘 / 内存
- 段（Segment）：ES 的思路，新增文档生成新段，后台合并，避免修改原有倒排（倒排不适合原地更新）
- 停用词过滤：
的、了这类高频词不建索引，减少巨大的 posting list
6.优缺点
优点：
1.全文关键词检索速度极快 核心优势。查询时不需要遍历所有文档，直接通过词条找到对应的文档列表，只处理相关文档，海量文本场景下远快于正排。多关键词检索可利用有序 posting list 做双指针交 / 并集。
2.支持相关性排序 倒排记录表可预先存储词频 TF、文档内位置等信息，方便 BM25 等算法快速计算相关度，实现按匹配程度排序，适合搜索引擎。
3.支持短语检索、高亮 posting 中保存词条在文档里的位置信息，可判断多个词是否连续相邻，支持短语搜索，也能定位文本用于结果高亮。
4.可压缩存储 docid 采用 delta 差值编码，能大幅减小 posting list 占用磁盘空间，降低 IO 开销。
缺点：
1.写入更新成本高 新增 / 修改 / 删除文档时，需要更新多个词条对应的倒排链表。
- 修改一篇文档，该文档内每一个词的 posting 都要改动；
- 传统倒排不适合原地修改，所以 ES 采用只读 segment，删除只是打标记，后台异步 merge，存在一定延迟。
2.索引占用额外存储空间 除原始文档数据外，还要存储词典、posting list、词频、位置信息。文档越多、分词越细，索引体积越大。
3.精确筛选、按文档属性查询不占优势 适合词检索；如果是按文档 ID、文档时间、数值字段过滤，不如正排 / 数据库 B + 树索引高效。
4.多词长查询开销可能变大 如果查询词是 “的、是” 这类高频停用词，posting list 会非常巨大，链表求交运算会变慢，一般需要停用词过滤优化。
5.构造索引耗时 建索引阶段，需要遍历所有文档、分词、统计词频、构建词条映射，大数据量下构建索引耗时较长。
7.适合场景
✅ 适合：搜索引擎、站内检索、全文检索（ES、Solr、SQLite FTS5），读多写少场景
❌ 不适合：频繁大量更新、只做按 id / 数值查询、小数据简单查询
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/haokan123456789/article/details/168342646
