嵌套循环连接算法和基于块的嵌套循环连接算法适用于内连接、左外连接、半连接、反半连接等语义的处理。
（2）排序归并连接算法
排序归并连接算法又称归并排序连接算法，简称归并连接算法。这种算法的步骤是：
①为两个表创建可用内存缓冲区数为M的M个子表，将每个子表排好序。
②读人每个子表的第一块到M个块中，找出其中最小的先进行两个表的元组的匹配，找出次小的匹配……。
③依此类推，完成其他子表的两表连接。
归并连接算法要求内外表都是有序的，所以对于内外表都要排序。如果连接列是索引列，可以利用索引进行排序。归并连接算法适用于内连接、左外连接、右外连接、全外连接、半连接、反半连接等语义的处理。
（3）Hash连接算法
基于Hash的两表连接算法有多种，常见的有3种：
①用连接列作为Hash的关键字，对内表进行Hash运算建立Flash表，然后对外表的每个元组的连接列用Hash函数求值，值映射到内表建立好的Hash表就可以连接了；否则，探索外表的下一个元组。这样的Hash连接算法称为简单Hash连接（Simple Hash Join，SHJ）算法。
②如果把内表和外表划分成等大小的子表，然后对外表和内表的母个相同下标值的子表进行SHJ算法的操作，可以避免因内存小反复读入内外表的数据的问题。这样的改进算法称为优美Hash连接（Graee Hash Join，GHJ）算法。
……
展开
