数据库中的表连接算法
单表扫描算法
常用的单表扫描算法
- 全表扫描表数据
- 局部扫描表数据
两表连接算法
基本的两表连接算法
循环
简单的二重循环。
for row1 in t1:
for row2 in t2:
if row1, row2 satisfies join conditions:
join row1, row2
这里是以元组为单位的连接。
但是元组是从一个内存页面获取过来的，而内存页面是通过以块为单位申请的多个。
然后改进一下就成了以块为单位读入，这样一次读取多个页面。
还有基于索引做改进，因为索引中的元祖相同值都放在一起，可以有效减少 IO。 然后查找索引还能加速，O(logn)？
排序归并连接算法
这个没怎么看懂，好像归并排序一样，从最小的开始并起来。那么为什么要选有序的呢？
Hash 连接算法
用连接列作为 Hash 关键字，对内表建立 Hash 表，然后对外表 Hash，一映射就能连接了。 这样乍一看效率是非常高的，如果能保证桶的分布均匀的话，不过太消耗内存。O(n)？ 然而 MySQL 中只有第一种算法。