"[链接] [链接]7.1 有序归并我们已经多次提到过有序归并，比如第二章中讲有序组表的追加时就用到这个算法，它可以用于实现大集合的交并差运算。以并集为例写出来的算法逻辑大体如下： A B C .."

279400248
乾学院 50 号会员
2 回帖 • 533 浏览 • 2 年前

【性能优化】7.1 [归并与连接] 有序归并

图书

7.1 有序归并

我们已经多次提到过有序归并，比如第二章中讲有序组表的追加时就用到这个算法，它可以用于实现大集合的交并差运算。以并集为例写出来的算法逻辑大体如下：

	A	B	C	D
1	func		=file("A.btx").cursor@b()	=file("B.btx").cursor@b()
2			=C1.fetch(1))	=D1.fetch(1)
3		for	if C2==null && D2==null	break
4			else if C2==null	>r=D2,D2=D1.fetch(1)
5			else if D2==null	>r=C2,C2=C1.fetch(1)
6			else if C2.id<D2.id	>r=C2,C2=C1.fetch(1)
7			else if C2.id>D2.id	>r=D2,D2=D1.fetch(1)
8			else	>r=C2,C2=C1.fetch(1),D2=D1.fetch(1)
9			return r
10	return cursor@c(A1)

数据表 A 和 B 都按 id 字段有序，从游标 C1 和 D1 中分别取出一条记录，比较出哪条记录的 id 更小，保存这条记录准备返回，并继续读取该记录所属游标，反复这个动作直到把两个游标的数据都取完。返回的游标就是两个数据集针对 id 字段计算出的并集。

计算交集，可以改成仅在相等时才返回数据，并且有一个游标结束时循环就结束了。差集也可以类似地实现。这个算法也可以推广到 n 个表的情况，代码会更复杂。

有序归并还可以用于实现连接运算，以内连接为例的算法逻辑：

	A	B	C	D
1	func		=file("A.btx").cursor@b()	=file("B.btx").cursor@b()
2			=C1.fetch(1))	=D1.fetch(1)
3		for	if C2==null \|\| D2==null	break
4			else if C2.id<D2.id	>C2=C1.fetch(1)
5			else if C2.id>D2.id	>D2=D1.fetch(1)
6			else	=new(C2,D2)
7				>r,C2=C1.fetch(1),D2=D1.fetch(1)
8				return D6
9	return cursor@c(A1)

算法逻辑和交集运算很像，全连接和左连接了可以类似实现，调整中间判断代码即可。同样也可以推广到 n 个表的情况。

有序归并算法只要把两个表都遍历一次就可以完成，即使是大数据表，也不必借助缓存文件。如果两个表的规模分别是 N 和 M，则复杂度为 O(N+M)。无序时实现集合或连接运算，不做优化时要两两比较，复杂度将会是 O(N*M)，远远大于 O(N+M)。数据库通常使用的是上一章讲过的哈希分堆算法，复杂度可以下降 K 倍（K 是哈希值的平均重复数量），但一般仍然会远大于有序归并算法。而且对于大数据的外存运算，哈希分堆会还产生缓存文件的读写动作，以及我们多次提过的可能运气不好的情况。利用有序后的归并算法有巨大的性能优化。

SPL 把集合运算和连接运算的有序归并算法都实现了：

	A
1	=file("A.btx").cursor@b()
2	=file("B.btx").cursor@b()
3	=[A1,A2].merge@u(id)
3	=[A1,A2].merge@i(id)
3	=[A1,A2].merge@d(id)

merge 函数的选项 @u、@i、@d 分别表示并集、交集和差集。

	A
1	=file("A.btx").cursor@b()
2	=file("B.btx").cursor@b()
3	=joinx(A1,id;A2,id)
3	=joinx@1(A1,id;A2,id)
3	=joinx@f(A1,id;A2,id)

无选项、@1、@f 的 joinx 函数分别表示内连接、左连接和全连接。

merge 和 joinx 都会假定作为参数的游标已经有序，针对无序游标执行这两个函数会得到错误的计算结果。

这两个函数都是延迟游标，需要再定义进一步的计算。

除了外键关联外，常见的连接运算还有同维关联和主子关联两类。同维关联是一对一的，两个表用主键关联。主子关联则是主表的主键和子表的前一部分主键关联，是一对多的。这两种关联的双方都和主键相关，如果数据按主键有序，就可以采用低复杂度的有序归并算法。上一章讲过的外键关联，在大维表对主键有序时也能获得高性能。

数据表对主键有序是实现高性能连接运算的关键，而且仅对主键有序就足够了，满足这个前提的成本并不是很高。在 SPL 中，我们会假定缺省情况下外存数据表都对主键有序，只有个别用于特殊查找目标的数据表才会另行排序。

关系代数对连接运算的定义过于简单（笛卡尔积再过滤），并没有涉及主键，严格实现这个定义时，理论上不能假定关联键的有序性，也就不能采用这些优化算法。而且关系代数的理论无序性也很难保证数据表对任何字段有序，数据库即使想在工程优化中实现也比较困难。

【性能优化】7.2 [归并与连接] 分段归并
 【性能优化】前言及目录

数据蒋堂(66)