连接运算三大类算法的适用条件

两张表做连接运算，三大类算法解决的是不同前提条件下”怎么避免真的 做完整笛卡儿积再筛选”这个问题。嵌套循环连接是最基础的做法：外层 循环遍历表r的每条记录，内层循环遍历表s的每条记录，逐对比较是否 满足连接条件——不需要任何前提（不要求排序、不要求索引），因此 最通用，但代价随两表元组数的乘积增长，效率最低；它有两个改进版本： 若表s在连接属性上已有索引，改用索引嵌套循环连接，内层不用扫全表 而是直接查索引；若按数据块而非单条记录做嵌套（块嵌套循环），能减少 磁盘块的重复读取次数。哈希连接适合等值连接和自然连接：用哈希函数 把两表的记录按连接属性分到多个桶里，只需要比较落在同一个哈希桶 里的记录对，天然避免了大量不必要的比较，选较小的表建哈希表效率 更高；当内存不足以一次装下整个哈希表时，还有磁盘哈希连接、Grace Hash Join等变种把数据分块处理。归并连接要求两张表都已经按连接 关键字有序排列（若本来无序，先排序再归并，即排序归并连接；若已建 索引，可以借索引间接获得有序访问，即索引归并连接），归并连接对 每张表只需要读一次，是三类里综合效率通常最高的，但前提”两表都 有序”往往需要额外付出排序或建索引的代价才能满足。三类算法的选型 本质是：完全没有额外结构可用时退而求其次用嵌套循环，有索引优先 利用索引，数据能排好序时归并连接通常最优。

结构图：

flowchart TD
    A[连接运算实现] --> B[嵌套循环连接<br/>无前提, 效率最低]
    A --> C[哈希连接<br/>适合等值/自然连接, 用哈希桶避免全量比较]
    A --> D[归并连接<br/>要求两表按连接键有序, 每表仅读一次]
    B --> B1[索引嵌套循环: 内层用索引替代全表扫描]
    B --> B2[块嵌套循环: 按块而非记录嵌套, 减少I-O]
    D --> D1[排序归并连接: 先排序再归并]
    D --> D2[索引归并连接: 借索引获得有序访问]