数据库-实现篇 第十六讲

两趟扫描算法的基本思想

1. 整个关系一元操作的问题：任何一个元组需要与所有元组进行比较，才能确定最终结果。这些需要内存
   内存不够存储整个关系怎么办？？——两趟 / 多趟算法
2. 两趟算法基本思路：
   （1）第一趟：划分子集，使子集具有某种特性（有序/具有相同散列值）。处理好之后将结果写回磁盘
   将磁盘上的数据重新建立数据结构
   （2）处理全局性的内容操作。多子集归并、相同散列值操作
   

两阶段多路归并排序 TPMMS

1. （1）内排序问题：待排序数据可一次性装入内存中
   插入排序、选择排序、冒泡排序
   （2）外排序问题：待排数据不能一次性装入内存
2. 算法思路：
   （1）第一趟：划分为子集合并子集排序
   （2）第二趟：各子集归并，纵向处理
3. 算法复杂性：3B® / 4B®
4. 算法应用条件：
   子集合数<Bmemory
   子集合块数<Bmemory
   大数据集块数<Bmemory*Bmemory

大数据集块数>Bmemory*Bmemory ,则可以采用多趟归并排序算法

基于排序的两趟扫描算法

1. 去重复操作
   （1）第一趟，划分子集并进行子表排序；
   第二趟：归并阶段，在排序的基础上直接将重复记录剔除不输出；
   （2）算法复杂性：3B® / 4B®

2. 分组聚集操作 GROUP BY
   （1）第一趟，划分子集并进行子表排序；
   第二趟：归并阶段，在排序的基础上，将不重复的记录作为新分组输出，将重复的记录进行分组聚集计算；
   （2）算法复杂性：3B® / 4B®

3. 基于排序的并、交、和、差
   （1）
   
   （2）交运算
   都需要两趟，需要处理出现次数或去重复
   第一趟：划分R和S的子表并排序；
   第二趟：R和S的输入之间按要求输出

（3）差运算
都需要两趟，需要处理出现次数或去重复
第一趟：划分R和S的子表并排序；
第二趟：R和S的输入之间按要求输出

（4）基于排序的连接运算

基于散列的两趟扫描算法

1. 基本思想：将大数据集划分为若干个子集，将大数据集上的操作转换为子集上的操作

第一趟：散列函数，将原始关系均衡地散列成M-1个子表，并存储。相同散列值的元组一定被映射到相同子集合
第二趟：用另一个散列函数将字表读入内存，在内存当中进行不同操作的处理

散列函数的选择和操作有关

3. 去重复操作
   （1）
   第一趟：将原始关系通过hp散列成M-1个子表，并存储
   第二趟：处理每一个字表，用另一个散列函数hr形成散列数据结构，进行去重复操作
   hp：计算元组部分属性值mod M
   hr：计算整个元组的值mod M
   （2）
   算法复杂性：3B® / 4B®

4. 分组属性
   （1）依据分组属性进行散列
   第一趟：将原始关系通过hp散列成M-1个子表，并存储
   第二趟：处理每一个字表，用另一个散列函数hr形成散列数据结构，进行分组聚集操作

hp：计算分组属性值mod M
hr：以分组属性的二进制位串重新计算值，然后MOD M
（2）
算法复杂性：3B® / 4B®
（3）核心思路：

5. 基于散列的并、交、差操作

6. 基于散列的连接操作
   （1）划分子表
   （2）存储块映射