【性能优化】3.8 [外存查找] 多索引归并
3.8 多索引归并
我们在前几节解释过多个索引不能同时使用，对两个字段分别建立索引后，在针对这两上字段的联合条件查询也只能使用其中一个索引，而另一个字段的条件仍然要遍历。
其实这个说法也不尽然，索引查询算法上做一些优化，还是能够一定程度地让多个索引配合工作。
为叙述方便，我们把满足 x 的记录集合记为 S(x)。假定表上字段 A 和 B 上都建有索引，我们要查找出 S(A==a && B==b)。使用 A 的索引能够快速定位出 S(A==a)，但要从中再找出属于 S(B==b) 的记录，却无法利用 B 的索引了。反之也是，可以用 B 的索引快速找出 S(B==b)，而无法继续在其中使用 A 的索引。
通常，索引中存储的记录物理位置也是有序的，也就是说 A 的索引中，存储的 S(A==a) 的记录物理位置是从小到大排序的；B 的索引也是类似。这一点在建立索引时很容易满足，甚至可以说天生就会被满足，因为排序时一般不会改变同值成员原来的次序。
利用这一点，可以在查找 S(A==a && B==b) 时同时使用 A 和 B 的索引。
过程并不复杂，用 A 的索引找出 S(A==a) 构成的游标，B 的索引找出 S(B==b) 构成的游标，这两个游标都对记录的物理位置有序，那么，只要用归并算法求它们的交集就可以得到 S(A==a && B==b) 了。这相当于只要把 S(A==a) 和 S(B==b) 都遍历一次即可，可以同时使用两个的索引。
但是，这个算法在复杂度上不一定比在 S(A==a) 中遍历计算 B==b 是否成立更有优势，因为后者只需要针对 S(A==a) 一个集合遍历，而刚才的算法要遍历 S(A==a) 和 S(B==b) 两个集合。
这种方法的优势在工程方面，归并求交集时不需要读出原数据表的记录来计算 B==b 是否成立，只需要对比索引即可。而索引块有可能已经在内存中，或即使在外存也是连续存储、只有两个列（被查找键和物理位置）、行存格式，读取性能要远好于多个字段、存储不连续、列存格式的原数据集，这样归并对比的性能就会好于读出记录再做判断。
如果我们选择 S(A==a) 和 S(B==b) 中较小的那个作为基准去归并另一个较大的，这样只要小的已遍历完就可以停止归并了，大的中尚未遍历完的成员都可以放弃了。这样总的遍历次数也不会很大。 而建索引时通常能够知道 S(A==a) 的记录数。
这种方法当然也适用于更多个字段上都有条件的情况。
SPL 中已经实现了这个机制，对于写在游标上形如 A==a && B==b && …的多字段条件，SPL 会自动在给出的索引文件列表中找出可以利用的索引并实施归并，不需要程序员干预。
