「智能」/經濟型數據存儲技術？

Question

我想存儲數百萬條數據線，看起來像這樣：

key，value

key是在（0〜5,000,000）的範圍內的整數;所有的價值都是獨特的

value是一個無符號INT16值（0到65535）

關鍵是要存儲的數據，同時服用的磁盤空間量最少，然而，能夠查詢該數據。你能想到任何有助於數據存儲的算法/智能方案嗎？

只是在它的問題的情況下，我使用Linux。

Answer 1

一種選擇是，如果鍵值是不重要的數據，而是僅僅索引數據利用位平面文件（帶有描述性標題）。每16位是一個值，然後第n個值將從頭部末尾開始（n-1）* 16位。

另外，如果鍵值事情做，10MB左右的設置平面文件將允許整個密鑰空間存儲不存儲實際的密鑰。位於（n-1）* 16偏移量的16位將是該鍵的值。

這很可能是用於存儲的最小的空間密集的方法，因爲這將是隻有被逐字所需的數據。只（不過，如果你只說100K值感興趣，一個擁有500萬的一個關鍵你有很多浪費的空間，這將不是與實際鑰匙在那裏結束了，價值尋址系統，所以這種方法實現對套緊緊地組合值或者很多很多的數字最低的磁盤存儲（以約200萬大關）。

Answer 2

你有沒有考慮使用專爲移動設備，如SQL Server精簡，或其他類似數據庫的數據庫？這些將在磁盤上佔用很小的空間，同時仍然提供您需要的全部搜索功能。

緊湊型數據庫引擎的另一個例子是KeyDB對於Linux：

http://3d2f.com/programs/11-989-keydb-download.shtml

Answer 3

你打算如何使用存儲的數據？用隨機或順序訪問嗎？順序訪問，你可以使用任何歸檔算法，如LZMA。隨機存取不會離開你一個很大的空間改善。

你可以看到這個數據的任何模式？例如，如果相鄰的鍵/值之間的差異是往往小，你可以存儲只有p分歧。以及其他可能的方法。

[編輯]你也可以檢查網絡通信用於數據壓縮技術
[EDIT1]，你可以檢查這個谷歌代碼Integer Array Compression項目

Answer 4

這取決於操作和數據。我首先推薦「只使用一個數據庫」（一個簡單的key-value存儲諸如BDB /的Ehcache [閱讀：Key Value store]，例如:-)

密米爾之泉也有一個很好的答案如果所有的按鍵都用過的。

如果密鑰鄰近常數/只讀和只一個相對小百分比的鍵的被使用，考慮使用（基於磁盤的）Heap數據結構的（非常相似的數組基堆;堆不需要基於陣列）。羅伯特·塞奇威克從80年代末開始有一本很好的書，其中有一本精簡的實現，但我忘記了這個名字。與使用鍵比例較小的扁平索引相比，堆將更有利，並且滿載時的存儲需求會更差。

（如果摘錄，所使用的方法可以交換和/或與索引/排序的葉節點的值的混合堆可用於[用霍夫曼編碼或諸如此類的東西沿]，但只是增加得多併發症 。保持簡單......因此現有鍵/值存儲的第一個建議;-)

快樂的編碼。