嵌套循环连接

嵌套循环连接（Nested loop join）是通过嵌套的循环语句把多个表连接起来的简单算法，SQL中的连接操作是数据库管理中重要的一环，

算法内容 
两个关系数据库表R和S通过如下的方法连接在一起：
   For each tuple r in R do
      For each tuple s in S do
         If r and s satisfy the join condition
            Then output the tuple <r,s>
这种算法将会从硬盘中读取  nr*bs+ br 个页， br 和 bs 是R和S表所占用的页的个数， nr 是R表中的记录数。

这种算法的IO次数为 ，

改进方法 
这种算法可以通过更改循环的嵌套方式减少硬盘的访问次数到 br*bs+ br 次。 对于R表的每一页，S的每一个记录只需要被读一次。
   For each block block_r in R do
      For each tuple s in S do
         For each tuple r in block_r do
            If r and s satisfy the join condition
               Then output the tuple <r,s>

電腦科學小作品
数据库算法