数据库-实现篇 第十六讲

两趟扫描算法的基本思想

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

两阶段多路归并排序 TPMMS

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

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

基于排序的两趟扫描算法

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

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

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

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

基于散列的两趟扫描算法

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

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

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

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

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

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

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

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