（Postgres）搜索引擎剖析
内容提要
本文介绍Postgres全文搜索的倒排索引原理：以词项为键映射到文档ID的倒排列表，支持并集、交集快速查询；包含词项字典、倒排列表及可选的位置和词频数据，用于短语查询和BM25评分；索引通过分词、词干化、停用词处理构建，采用分段存储、合并和墓碑机制应对增删改；在Postgres中需处理ctid、WAL、VACUUM、事务可见性及查询规划等集成问题。
延伸解读
倒排索引的压缩与查询优化
倒排列表通常经过排序和压缩以节省空间。如果文档ID密集，可以存储差值而非绝对值，例如30万文档中10万包含某词，平均间隔仅3，用2位即可表示。更密集时可用位图，每文档1位。压缩后，并集和交集操作可在O(n)时间内完成，位图形式更能利用CPU向量指令一次处理128至512位，极大加速查询。
位置与词频数据的存储权衡
位置数据用于支持短语查询和跨度查询，词频数据用于BM25评分。这些数据通常与倒排列表分开存储，因为大多数查询不需要它们，按需加载可减少I/O。索引大小因此变化：无位置和评分数据的索引约为语料库的20%，而包含位置和词频的英文索引可达30-50%，代码搜索索引甚至高达300%。
分段合并与删除的代价
索引由多个不可变分段组成，新文档先写入可变分段，满后转为不可变分段。分段过多会降低查询效率，因此需要合并。合并是线性操作，但需大量磁盘I/O和临时空间，可能读写数十GB。删除通过墓碑标记实现，被删文档仍占空间并浪费CPU，只有合并时才能清除。更新即删除加插入。
Postgres集成中的关键挑战
在Postgres中实现倒排索引需处理多项集成问题：索引需存储ctid以定位行，并作为WAL日志关系以支持复制和备份；VACUUM需清理指向死元组的索引项，VACUUM FULL会改变ctid需更新；事务可见性要求索引只返回已提交且可见的结果；查询规划器需决定何时使用全文索引、b-tree或两者结合，多列全文条件宜用CustomScan在索引内过滤。
Q&A
为什么传统的B树索引不适合全文搜索？
B树索引按列值的全序排列，能快速处理精确值、范围或前缀查询，但无法匹配字符串中间的内容。例如，使用LIKE '%Royal'会检查每一行，效率低下。全文搜索需要倒排索引来根据单词快速定位文档。
倒排索引的基本结构是什么？
倒排索引至少包含词项字典和倒排列表。词项字典映射所有词项到倒排列表；倒排列表存储包含该词项的文档ID。可选地，还可以包含位置数据和词频数据，以支持短语查询和评分。
倒排索引如何支持短语查询？
通过存储位置数据，倒排索引可以记录每个词项在文档中出现的位置。短语查询要求词项按特定顺序出现，位置数据使得索引能够验证词项是否相邻或在一定距离内，从而支持短语和跨度查询。
BM25评分是什么？它如何工作？
BM25是一种评分公式，用于评估文档与查询的相关性。它结合词频（词项在文档中出现的次数）和逆文档频率（词项在所有文档中的稀有程度），对每个查询词项计算子分数并求和。BM25认为稀有词项更重要，且文档中词项出现次数越多，相关性越高。
倒排索引如何处理文档的删除和更新？
删除文档时，倒排索引不会立即从倒排列表中移除文档ID，而是创建一个墓碑标记，查询时过滤掉这些ID。更新文档相当于先删除旧版本（打墓碑）再插入新版本。墓碑只有在段合并时才会被清理，以节省空间和计算资源。
在Postgres中集成倒排索引需要解决哪些问题？
需要处理ctid映射（将文档ID映射到行标识符）、WAL日志记录（确保复制和备份）、VACUUM（清理死行并更新ctid）、事务可见性（确保查询只返回已提交的文档）以及查询规划（决定何时使用全文索引、B树或两者结合）。此外，还需要后台任务进行段合并。
