在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

回答