implement：一個字符串到字符串數據庫

Question

就像std::unordered_map<std::string, std::string>但所有的數據應該被存儲在在磁盤而不是在內存中。

據我所知，應該完成兩個部分：索引和存儲。我學習了一些關於索引的數據結構，例如Linear-Hash或B-Tree，並且寫入磁盤上的int-> int數據庫並不難。問題在於存儲。

對於整數，所有記錄大小相同。一旦我們通過索引獲得了記錄的位置，我們就可以輕鬆地提取，修改或懶惰刪除。但對於字符串來說，記錄的大小很靈活。它應該有（至少）存在以下問題：

1. 的put（）更長的字符串：我們不能簡單地覆蓋舊的記錄，我們戴夫做德爾（）和put（）和老唱片的空間被浪費了。

2. del（）：舊記錄的空間也被浪費了，不能再次使用。 （也許我們可以用垃圾回收器收集已刪除的空間，但是它會佔用額外的空間併產生碎片）

3. 對於int-> int數據庫，浪費幾個整數的空間不是一個大問題。但字符串更長，它會浪費更多的空間。

我需要一些建議/提示來解決問題。

Answer 1

您可以舉例說明文件系統如何管理可變大小的文件。

它們以大約幾千字節的固定大小塊分配文件空間，並將這些塊鏈接在一起以形成任意長度的整個文件。

如果您需要擴展文件，請分配並鏈接更多塊。如果您需要縮小或刪除它，請取消鏈接並釋放一個或多個塊。

關於這裏唯一引人注意的碎片是內部的，每個文件最後一個塊的浪費空間。

如果您使用文件實現此目的，其中每個塊都是可能是大文件的一部分，或者是其自己的文件，則不需要立即刪除/釋放它。您可以在控件/元數據中將其標記爲空閒，然後再使用。您可以實施壓縮（刪除所有空閒塊）作爲不經常執行的獨立操作。

Answer 2

首先實現一個映射器。每當你得到新的字符串，將它們順序存儲在一個文件中，並將它們的位置存儲在地圖上。

Answer 3

對我來說，這聽起來像一個鍵/值存儲的定義。你可以使用任何你喜歡的系統。從Oracle的Berkeley DB到Cassandra或Riak。