加入非常大的列表

讓我們先放一些數字：列表中最大的大約是100M記錄。（但預計將增長到500）。其他名單（其中5-6名）以百萬計，但在可預見的未來將低於100M。這些是總是基於一個單一的ID加入。並從來沒有任何其他參數。加入這樣的列表最好的算法是什麼？加入非常大的列表

我在分佈式計算的思路。有一個好的散列函數（循環散列類型，可以添加一個節點，並且沒有太多的數據移動功能），並將這些列表拆分爲幾個較小的文件。而且，因爲它們總是以共同的ID（我將哈希）加入，所以它會歸結爲加入小文件。也許可以使用nix連接命令。

DB（至少MySQL）將使用合併連接進行連接（因爲它將位於主鍵上）。我的方法會更有效率嗎？

我知道最好去測試看看。但鑑於這些文件的大小，它非常耗時。我想做一些理論計算，然後看看它在實踐中的表現。

對這些或其他想法的任何見解都會有所幫助。我不介意它是否需要稍微長一些，但更願意充分利用我擁有的資源。沒有一個巨大的預算:)

來源

2010-08-20 neal aise

也許基於Hadoop的解決方案（如HBase）可能有用嗎？ – 2010-08-20 08:17:12

是否訂購了所有的清單？小列表是否被排序？（如果是這樣，您可以使用不同的切片技術來分割處理）。其他相關問題 - 您擁有多少個CPU核心，每個處理節點有多少RAM，數據集消耗多少RAM以及是否有共享存儲？ Instinct是最好的選擇是將主列表拆分N（其中N是CPU內核的數量），然後加入其他文件的相關子列表。我認爲你是正確的使用哈希 - 一個數據庫和B樹索引只會回報，如果你需要以後重複獲取數據。 – JulesLt 2010-08-20 08:23:39

@JulesLt我有選擇。所以，如果我想讓他們訂購，我將不得不維護訂單，因爲新行進入/刪除。將考慮你的建議和稍後回答的CPU數學。 @ar：謝謝你會查找它！ – 2010-08-20 08:36:13

使用數據庫。它們設計用於執行連接（當然有正確的索引！）

來源

2010-08-20 08:15:23

但除非我做了一些分片。數字相當高。所以我會想象，我將不得不跨越數據庫的外部進行最終的合併 – 2010-08-20 08:31:23

1億行並不是那麼大。通常的經驗法則是考慮使用約5000萬行的表分區。 – 2010-08-20 08:41:34