在O（n）时间执行连接？

有没有办法在线性时间内连接2个表格？我听说这可以通过另一个数据结构（Hashtable）来完成，但我不确定如何做到这一点。我一直在想一个Join会涉及一个交叉产品，因此它是O（n^2）。在O（n）时间执行连接？

2011-04-05 Shankar

检查这一个http://en.wikipedia.org/wiki/Hash_join – Andrey 2011-04-05 20:21:13

[A （http://oreilly.com/catalog/9780596005733） – Pointy 2011-04-05 20:22:02

@Andrey和@Pointy：非常感谢你的链接:) – Shankar 2011-04-05 20:23:54

算法：

循环遍历表A.将所有项目散列，将它们添加到Join数组中。
循环遍历表B，检查每个项目是否在散列表中（Check-O（1）），如果没有，则添加到联接表。

2011-04-05 20:21:18

如果联接中使用的列上有索引，则它是线性的，因为索引允许按顺序遍历这两个表。（当然，这不包括摊销索引成本。）

散列连接将是排序线性的，尽管散列本身并不是免费的，并且当涉及的键很长时，成本也会上升。

2011-04-05 20:20:54 Pointy

感谢您的回复:) – Shankar 2011-04-05 20:24:19

确定 - 请注意而索引原则上可以执行线性时间连接，如果统计信息表明其中一个有效表比另一个有效表小得多，则服务器可以决定进行散列连接。 – Pointy 2011-04-05 20:42:08

是的，必须检查2个表的大小以获得更好的效率。 – Shankar 2011-04-05 20:48:52

这取决于连接的类型。交叉连接总是会是O（n^2），因为它必须产生O（n^2）个记录。如果使用正确的数据结构，可以使用更好的复杂性（O（n log（n））或甚至可以摊销O（n））来完成等连接。

2011-04-05 20:22:27 NPE

我一直在寻找自然连接的时间复杂度 – Shankar 2011-04-05 20:25:09

连接的类型并不重要。用两个不相交列表为每个记录添加一个值为0的共同虚拟列。自然连接的复杂性仍然是二次的，因此是最坏情况的估计。 – 2011-04-13 22:36:11

您可以通过使用散列表在另一个表的ID中查找记录，以接近O（n）的方式连接两个表。

嗯，实际上该操作将接近为O（n + m），其中Ñ和米是在两个表中的项数。您将首先遍历一个表中的记录以从该表中的键构建哈希表，然后循环遍历另一个表以在每个记录的哈希表中查找匹配项。

查找散列表中的项目不是O（1）操作，但它很接近。随着更多的数据你会有更多的散列冲突，所以一些查询需要做多个比较。

2011-04-05 20:26:41 Guffa

非常感谢回复 – Shankar 2011-04-05 20:28:12

很久以前，主要的数据库供应商不推荐使用散列索引。因此，在O（max（n，m））时间内连接2个表格实际上并不重要。对于标准B树索引，连接复杂度为O（min（n，m）* log（max（n，m））。

2011-04-13 22:30:11

回答