系统概论王珊_系统概论第五版_系统概论(7)

参见爱课程网9.1节《连接操作的实现 1 --嵌套循环》 连接操作的实现（续） （2）排序-合并算法 sort-merge join 或merge join 如果连接的表没有排好序，先对Student表和SC表按连接属性Sno排序 取Student表中第一个Sno，依次扫描SC表中具有相同Sno的元组 当扫描到Sno不相同的第一个SC元组时，返回Student表扫描它的下一个元组，再扫描SC表中具有相同Sno的元组，把它们连接起来 重复上述步骤直到Student 表扫描完 连接操作的实现（续） 座机电话号码1 … 座机电话号码2 … 座机电话号码3 … 座机电话号码5 … . . . 座机电话号码1 1 92 座机电话号码1 2 85 座机电话号码1 3 88 座机电话号码2 2 90 座机电话号码2 3 80 . . . 图9.2 排序-合并连接方法 连接操作的实现（续） Student表和SC表都只要扫描一遍 如果两个表原来无序，执行时间要加上对两个表的排序时间 对于大表，先排序后使用排序-合并连接算法执行连接，总的时间一般仍会减少 参见爱课程网9.1节《连接操作的实现（2）--排序合并 》 连接操作的实现（续） （3）索引连接 index join 算法 步骤： ① 在SC表上已经建立属性Sno的索引。

② 对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组。 ③ 把这些SC元组和Student元组连接起来 循环执行②③，直到Student表中的元组处理完为止 参见爱课程网9.1节《连接操作的实现 4 -- 索引连接 》 连接操作的实现（续） （4）Hash Join算法 把连接属性作为hash码，用同一个hash函数把Student表和SC表中的元组散列到hash表中。 划分阶段 building phase, 也称为partitioning phase 对包含较少元组的表 如Student表 进行一遍处理 把它的元组按hash函数分散到hash表的桶中 试探阶段 probing phase,也称为连接阶段join phase 对另一个表 SC表 进行一遍处理 把SC表的元组也按同一个hash函数（hash码是连接属性）进行散列 把SC元组与桶中来自Student表并与之相匹配的元组连接起来 连接操作的实现（续） 上面hash join算法前提：假设两个表中较小的表在第一阶段后可以完全放入内存的hash桶中 参见爱课程网9.1节《连接操作的实现 3 --散列连接 》 第九章 关系查询处理和查询优化 9.1 关系系统的查询处理 9.2 关系系统的查询优化 9.3 代数优化 9.4 物理优化 *9.5 查询计划的执行 9.6 小 结 An Introduction to Database System

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25972-7.html