首页 -> 1.3 执行布尔查询
我们如何使用反向索引和基础的布尔检索模型执行查询呢？考虑执行一个简单的组合查询：
(1.1) Brutus AND Calpurnia
基于图1.3展现的反向索引上。我们：
- 在字典中找到Brutus
- 获得它的记录集
- 在字典中找到Calpurnia
- 获得它的记录集
-
取两个记录集的交集，如图1.5所示
交集操作是关键的一步：我们需要高效地对记录集取交集，这样才能快速的找到包含两个词的文档。（这个操作有时候叫做合并记录集：这个有点违反直觉的名字来自术语合并算法。合并算法是一组用来合并多个排序的列表的算法，这里我们采用的是逻辑与操作。）
使用合并算法来交叉处理记录列表是简单而高效的方法（参看图1.6）：我们维护两个列表的指针，同步的遍历两个记录列表，时间接近记录项目的总数。每一步，我们比较两个指针指向的docID。如果它们一样，我们就把docID放到结果列表，然后前进两个指针。反之，我们前进指向更小docID的指针。如果记录列表的长度是x和y，那么合并花费O(x+y)次操作。正式的来说，查询的复杂度是Θ(N)，N是文档集中的文档数。我们的索引方法得到了一个常数时间，但是跟线性扫描的时间复杂度没有什么区别，但是在实践中这个常数时间非常巨大。要使用这个算法，关键是记录表要使用一个全局单一的排序方式来排列。使用docID的数字排序是简单的实现方式。
我们可以扩展交集操作来实现更复杂的查询，形如：
(1.2) (Brutus OR Caesar) AND NOT Calpurnia
查询优化是一个流程，选择如何组织操作，能用最少的操作完成一个查询。对于布尔查询，查询优化的一个主要的成分是记录表的访问顺序。什么才是查询处理的最佳顺序？考虑下面的一个查询包含了t个词的AND查询，例如：
(1.3) Brutus AND Caesar AND Calpurnia
对于t个词中的每一个，我们需要获得它的记录集，然后对它们一起执行与操作。标准的做法是按照文档频率增加的顺序处理：如果我们从两个最小的记录集的交集操作开始，那么中间结果一定不会比最小的记录集大，这样我们好像总工作量就会最小。所以对于图1.3的记录表，我们执行如下的查询：
(1.4) (Calpurnia AND Brutus) AND Caesar
这是在字典中保存词频的第一个理由：这让我们可以在访问任何记录表之前根据内存内的数据决定操作顺序。
现在考虑更通用的查询优化问题，查询行如：
(1.5) (madding OR crowd) AND (ignoble OR strife) AND (killed OR slain)
如前所述，我们得到所有词的频率，然后我们通过对对应的词频求和的方式大致评估每个OR操作结果的大小。然后我们可以按照尺寸增长的顺序执行查询。
对任意的布尔查询，我们必须评估和临时存储复杂表达式的中间结果。然而在大多数情况下，不管是因为查询语言的特性，还是因为这是用户输入查询的最常见类型，查询往往是纯粹的组合查询。在这种情况下，与其把合并记录集看作有两个输入和一个输出的函数，不如更有效率的把每个得到的记录列表和当前内存中的中间结果进行交集，中间结果的初始化可以装入词频最小的词的记录集。图1.7展示了这种算法。交集操作是不对称的：中间结果保存在内存，而要被交集运算的列表从硬盘读取。而且中间结果列表总是比其他的列表短，而且在大多数情况下短得非常突出。记录的交集可以按照图1.6的算法执行，但是当列表间的长度差非常大的时候，其他可选技术的机会就来了。交集可以利用对中间结果的损坏性修改，或者标志无效项目的方式来实施。或者对中间结果中的每个记录执行长记录列表中的二进制查找，这样也可以实现交集。另外的可能性是把长的记录表保存为哈希表，这样的话长记录列表中是否包含中间结果中的项目的计算就变成了常数时间，而不是线性的漫长的查找。然而这些可选技术很难和第5章讨论的记录列表压缩相结合。而且，当两个词都很普通的时候，标准的记录列表交集操作还是需要的。