如果再有人问你数据库的原理，把这篇文章给他( 十 ) _数据库

2) 保存哈希表到磁盘

3) 然后逐个哈希桶比较（其中一个读入内存，另一个逐行读取）。

合并联接
合并联接是唯一产生排序的联接算法。
注：这个简化的合并联接不区分内表或外表；两个表扮演同样的角色。但是真实的实现方式是不同的，比如当处理重复值时。
1.（可选）排序联接运算：两个输入源都按照联接关键字排序。
2.合并联接运算：排序后的输入源合并到一起。
排序
我们已经谈到过合并排序，在这里合并排序是个很好的算法（但是并非最好的，如果内存足够用的话，还是哈希联接更好）。
然而有时数据集已经排序了，比如：

如果表内部就是有序的，比如联接条件里一个索引组织表【译者注： index-organized table 】
如果关系是联接条件里的一个索引
如果联接应用在一个查询中已经排序的中间结果

合并联接

文章插图

这部分与我们研究过的合并排序中的合并运算非常相似。不过这一次呢，我们不是从两个关系里挑选所有元素，而是只挑选相同的元素。道理如下：

1) 在两个关系中，比较当前元素（当前=头一次出现的第一个）
2) 如果相同，就把两个元素都放入结果，再比较两个关系里的下一个元素
3) 如果不同，就去带有最小元素的关系里找下一个元素（因为下一个元素可能会匹配）
4) 重复 1、2、3步骤直到其中一个关系的最后一个元素。

因为两个关系都是已排序的，你不需要『回头去找』，所以这个方法是有效的。
该算法是个简化版，因为它没有处理两个序列中相同数据出现多次的情况（即多重匹配）。真实版本『仅仅』针对本例就更加复杂，所以我才选择简化版。
如果两个关系都已经排序，时间复杂度是 O(N+M)
如果两个关系需要排序，时间复杂度是对两个关系排序的成本：O(N*Log(N) + M*Log(M))
对于计算机极客，我给出下面这个可能的算法来处理多重匹配（注：对于这个算法我不保证100%正确）：
C

文章插图

哪个算法最好？
如果有最好的，就没必要弄那么多种类型了。这个问题很难，因为很多因素都要考虑，比如：

空闲内存：没有足够的内存的话就跟强大的哈希联接拜拜吧（至少是完全内存中哈希联接）。
两个数据集的大小。比如，如果一个大表联接一个很小的表，那么嵌套循环联接就比哈希联接快，因为后者有创建哈希的高昂成本；如果两个表都非常大，那么嵌套循环联接CPU成本就很高昂。
是否有索引：有两个 B+树索引的话，聪明的选择似乎是合并联接。
结果是否需要排序：即使你用到的是未排序的数据集，你也可能想用成本较高的合并联接（带排序的），因为最终得到排序的结果后，你可以把它和另一个合并联接串起来（或者也许因为查询用 ORDER BY/GROUP BY/DISTINCT 等操作符隐式或显式地要求一个排序结果）。
关系是否已经排序：这时候合并联接是最好的候选项。
联接的类型：是等值联接（比如 tableA.col1 = tableB.col2 ）？还是内联接？外联接？笛卡尔乘积？或者自联接？有些联接在特定环境下是无法工作的。
数据的分布：如果联接条件的数据是倾斜的（比如根据姓氏来联接人，但是很多人同姓），用哈希联接将是个灾难，原因是哈希函数将产生分布极不均匀的哈希桶。
如果你希望联接操作使用多线程或多进程。

想要更详细的信息，可以阅读DB2, ORACLE 或 SQL Server)的文档。
简化的例子
我们已经研究了 3 种类型的联接操作。
现在，比如说我们要联接 5 个表，来获得一个人的全部信息。一个人可以有：