两趟扫描算法 - zzyoga/JustTest GitHub Wiki

1.两趟算法的基本思路

第一趟：划分子集，并使子集具有某种特性，如有序或者相同的散列值等。先把原始数据读到内存中处理一遍再写回内存称为一趟。

第二趟：处理全局性的内容形成结果关系，比如多子集间的归并排序，相同散列值子集的操作等。

2.两阶段多路归并排序（Two Phase Multiway Merge Sort,TPMMS）：

我们的内存满足不了待排序块数，所以排序的基本思路是：将待排的磁盘块划分为 N个子集合，但是需要保证每个子集合能够完整的装入到内存中，并且内存可以采用内排序算法排好序重新写回磁盘。

那么我们将N个子集合排好序之后，问题就转换成了怎么将已经排好序的N个集合合并成一个整体的排序集合?这就是TPMMS的思想：各个子集之间归并排序。

（就是外排的归并算法）

算法的复杂性：读写磁盘的IO次数：4待排序磁盘块数（子集合排序排序阶段：读一遍，写一遍；归并阶段：读一遍，写一遍）。概算法的应用条件是子集合树<B(内存)；子集合的块数<B(内存)----->数据集的块数<B(内存)的平方。如果大于平方项的话，需要使用多趟的排序。

3.基于排序的两趟扫描算法

上面的两阶段多路归并排序是理解基于排序的两趟扫描算法的基础

我们看怎样基于TPMMS来做去重操作：第一趟是划分子表，并对子表进行排序，并且在排序的过程中直接将子表中重复的去掉。第二趟是归并阶段，在排序的基础上，直接将重复的记录剔除掉----不输出。 算法的复杂性和TPMMS一样

分组聚集操作：第一趟划分子表并进行子表排序；第二趟是归并阶段，在排序的基础上，将不重复的记录作为新的分组输出，将重复的记录进行分组聚集操作（因为重复的记录会连续的出现）。算法的复杂性桶TPMMS一致。

4.基于散列的两趟扫描算法

基本思想：将大数据集上的操作转换为某个子集上的操作。第一趟就是散列子表，用散列函数h将原始关系划分为M-1个子表，并存储。第二趟：处理每个子表用另外一个散列函数h，将子表读入内存中并建立内存结构，进行不同操作的处理。