存儲數十億整數的數據結構

在內存（RAM）中存儲數百萬/數十億條記錄（假設記錄包含名稱和整數）的最佳數據結構是什麼？最佳搜索時間（第一優先級）和內存有效性（第二優先級）？它是帕特里夏樹嗎？任何其他比這更好？存儲數十億整數的數據結構

搜索鍵是整數（比如32位隨機整數）。所有記錄都在RAM中（假設有足夠的RAM可用）。

在C，平臺的Linux ..

基本上我的服務器程序分配一個32位的隨機密鑰給用戶，我想存儲相應的用戶記錄，這樣我可以搜索/刪除有效的方式記錄。可以假定數據結構將被很好地填充。

來源

2009-07-29 Marc M

您是否在搜索名稱或號碼？或兩者？ – 2009-07-29 10:38:47

這組記錄是否經常更新，並且有多徹底？整數的分佈是什麼樣的？將所有名稱的哈希表安裝在您可用的內存中是否舒適？ – reinierpost 2009-07-29 10:43:50

取決於。

你想搜索名稱或整數？

這些名稱都大約相同嗎？

所有的整數是32位還是一些大數字thingy？

你確定這一切都適合內存？如果沒有，那麼你可能受到磁盤I/O的限制，內存（或磁盤使用率）不再是問題。

索引（名稱或整數）是否具有相同的前綴或是否均勻分佈？只有他們有共同的前綴，帕特里夏樹纔有用。

你是按順序查找索引（團伙查找）還是隨機查找索引？如果一切都是統一的，隨機的，沒有共同的前綴，散列已經是一樣好（這是不好的）。

如果索引是使用組合查找的整數，則可以查看基數樹。

來源

2009-07-29 10:41:51

很多問題都可以在RAM中適用。昨天我配置了一個帶有96 GB RAM的Dell，價格低於20K歐元 – 2009-07-29 11:33:41

我的猜測是B-Tree（但我可能是錯的...）：

B樹中都具有相當的優勢在替代實現時節點的訪問時間節點內，遠遠超出訪問倍。當大多數節點位於輔助存儲設備（如硬盤驅動器）時，通常會發生此問題。通過最大化每個內部節點內的子節點的數量樹的高度減少，平衡發生的次數減少，並且效率增加。通常這個值被設置爲使得每個節點在第二存儲器中佔滿整個磁盤塊或類似的大小。雖然2-3 B樹可能在主內存中有用內存，並且當然更容易到說明，如果節點大小調整爲爲磁盤塊的大小，則結果可能是257-513 B-樹（其中尺寸與較大的的冪相關）。

來源

2009-07-29 10:56:59 pageman

而不是散列，你至少可以使用基數開始。

對於任何特定問題，您可以比btree，哈希表或patricia trie更好地完成任務。將問題描述得更好一些，我們可以建議可能的工作

來源

2009-07-29 11:37:27

如果您只想用整數鍵進行檢索，那麼簡單的哈希表就是最快的。如果整數是連續的（或幾乎連續的）並且是唯一的，那麼一個簡單的數組（指向記錄的指針）甚至更快。

如果使用散列表，您希望爲預期的最終大小預分配散列表，以免重新散列。

來源

2009-07-29 16:31:54

存儲數十億整數的數據結構

回答

相關問題