查看“︁嵌套循环连接”︁的源代码

{{Orphan|time=2022-07-20T15:30:41+00:00}}
'''嵌套循环连接'''（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>
这种算法将会从硬盘中读取  n<sub>r</sub>*b<sub>s</sub>+ b<sub>r</sub> 个页， b<sub>r</sub> 和 b<sub>s</sub> 是R和S表所占用的页的个数， n<sub>r</sub> 是R表中的[[记录]]数。

这种算法的IO次数为 <math>O(|R||S|)</math>，<math>|R|</math><math>|S|</math>

== 改进方法 ==
这种算法可以通过更改循环的嵌套方式减少硬盘的访问次数到 b<sub>r</sub>*b<sub>s</sub>+ b<sub>r</sub> 次。 对于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>
{{Compsci-stub}}
[[Category:電腦科學小作品]]
[[Category:数据库算法]]