知识卡片
倒排索引：布尔查询即列表的集合运算
内容
倒排索引由字典（记录每个词对应的磁盘地址）和倒排列表（对每个词按文档号升序存放包含它的文档指针）组成。这个”升序排列”约定直接决定了布尔查询能被高效实现——AND是对多个倒排列表求交集，OR求并集，NOT求补集，升序列表求交并集只需像归并排序那样各自维护指针线性扫描。这把”检索”这个复杂问题转化成了对有序列表做归并这个已被研究透的基础操作。
参考来源
- 位置：第3章《索引》3.2节「倒排文件索引」（源文件：_chapter-text/ch03.txt）
- 结论依据：原文明确定义倒排索引由字典和倒排列表组成，且指出倒排列表按文档号升序存放使得AND/OR/NOT查询可以用线性归并高效实现，直接支持卡片论点。
- 原始内容："倒排文件索引还需要一个字典（lexicon）……倒排列表通常按照文档号升序的方式存放，因此对于倒排列表的归并（merge）操作可以按照列表长度的大小在线性时间内完成……将这两个单词对应的倒排列表……归并（或者严格地说，求交集）。"