厦门大学计算机科学系.ppt

概述 归并排序算法 简单的基于排序的连接算法 归并排序连接算法 9.4.3 基于排序的联接算法 基于排序的连接算法，首先将两个关系按照连接属性进行排序，然后按照连接属性的顺序扫描两个关系，同时，对两个关系中的元组执行连接操作。 由于数据库中关系的大小往往大于连接操作可用内存缓冲区的大小，因此，对关系的排序通常采用外存排序算法，即归并排序算法。 可以将基于排序的连接算法的执行过程与归并排序算法结合的算法，可以节省更多的磁盘IO，通常称为归并排序连接算法。 概述 简单的归并排序算法的执行可以分为两个阶段： 第一阶段：对关系进行分段排序，即首先将需要排序的关系R划分为大小为M个块的子表，其中，M是可用于排序的内存空间的个数，以块为单位，再将每个子表放入内存中采用快速排序等主存排序算法执行排序操作，这样可以获得一组内部已排序的子表。 第二阶段：对关系的子表执行归并操作，即按照顺序从每个排序的子表中读取一个块的内容放入内存，在内存中统一对这些块中的记录执行归并操作，每次选择最大（最小）的记录放入输出缓冲区中，同时删除子表中相应的记录。当子表在内存中的块被取空时，从子表中顺序读取一个新的块放入到内存中继续执行归并操作。 归并排序算法 图4.15 简单的归并排序算法的执行 归并排序算法 归并排序的过程如图4.15所示，其中同时对多个子表执行归并操作，因此，也称为两阶段多路归并排序。需要说明的是，第二阶段的归并操作执行的条件是关系的子表数量小于排序操作可用的内存的块数M，这样才能保证同时对所有子表进行归并操作。 因此，两阶段归并执行的条件是关系的大小Block(R)≤M2。如果关系的大小大于M2，则需要嵌套执行归并排序算法，使用三阶段或更多次的归并操作。 基于排序的连接算法，主要是对已经按照连接属性排序的两个关系，按照顺序读取关系中的块到内存中执行连接操作。 *代价计算* 假设在排序阶段使用的是两阶段多路归并排序，关系的大小满足条件Block(R)≤M2， Block(S) ≤ M2。这样，算法在排序阶段的执行代价包括对关系的子表执行排序所需的一次读（读子表数据）和一次写（子表排序结果写入磁盘）的代价2(Block(R)+Block(S))，以及多路归并时的读写代价2(Block(R)+Block(S))，而在归并连接阶段还需要对关系执行一次读操作，代价为Block(R)+Block(S)。因此，简单的基于排序的连接算法的执行代价为：Cjoin=5(Block(R)+Block(S))。 简单的基于排序的连接算法 图4.16 简单的排序连接算法 在简单的基于排序的连接算法中，归并连接阶段仅仅使用了内存缓冲区的两个块的空间，还有大量的空闲内存没有使用。因此，一种更加有效的归并排序连接算法被提出，其思想是将排序的第二阶段与归并连接阶段合并，即直接使用两个关系的排序子表执行归并连接操作，这样可以节省一次对关系的读写操作。 假设可用内存缓存区为M个块，算法首先对两个关系划分成大小为M个块的子表并排序，再从每个子表中顺序读取一个块调入内存缓冲区执行连接操作。这里要求两个关系的子表总数不超过M个。 归并排序连接算法 图4.17 归并排序连接算法示意图 归并排序连接算法在排序阶段的代价包括对子表的一个读写操作2(Block(R)+Block(S))，而在归并连接阶段仅需一次代价为Block(R)+Block(S)的读操作，因此，执行的总代价为： Cjoin=3(Block(R)+Block(S)) 这里注意，归并排序连接算法要求两个关系的子表数量，必须小于内存缓冲区的块数M，这样才能够保证归并阶段有足够的内存存放每个子表的一部分以执行连接。 因此，执行归并排序连接算法需要关系的大小满足： Block(R)+Block(S) ≤ M2 归并排序连接算法 散列连接算法，也称为哈希连接算法，基本的执行过程同样分为两个阶段： 第一阶段：使用同一个散列函数，对进行连接的两个关系R和S中的元组的连接属性值进行散列，在连接属性上具有相同键值的元组会出现在相同散列数值的桶中； 第二阶段：对两个关系中散列数值对应的桶中的元组执行连接操作。 假设可用的内存缓冲区为M块，散列时使用M-1个块作为桶的缓冲区（最多允许散列到M-1个桶），剩余的1个块作为扫描输入关系的缓冲区。 9.4.4 散列连接算法 在算法的第一个阶段中，使用内存将关系R和S散列到M-1个桶中，分别得到写入文件中的R1,…,Rm-1和S1,…,Sm-1，这个过程需要对两个关系执行一次读写操作，代价为2(Block(R)+Block(S))。 在第二个阶段中，每次选取两个关系中具有相同散列值的桶Ri和Si放到内存中执行连接操作。假设S为较小的关系，由于在对桶连接时必须有一