在ssd上創建trie。如何管理對象移動到其他位置？

Question

我需要在ssd上創建一個trie。我不能使用太多的內存，因爲這個內存很大，但是4 GB內存沒有問題。

目前，我認爲這樣做是通過以下方式：

• 使用一個內存映射文件
• 有對象序列化與protobuf的，不斷變化的指向其他對象以文件的位置和長度

現在我正在尋找可以提供幫助的工具。當對象（節點）變大時我遇到問題。我需要在這個對象的文件中找到一個新的位置，改變這個對象的所有鏈接。然後我在文件中留下了空白。然後，我需要壓縮我的樹並更改所有對象的所有位置以縮小一些間距。在每個物體之後留下一些空間會導致非常多的空間要求。

你知道圖書館或有一些提示，以解決這個問題，或可以幫助編程這一切？

Answer 1

我想在這裏提供一個新的角度來解決這個問題：爲什麼你不在SQLite數據庫中存儲trie-nodes？ SQLite速度快，測試良好，功能豐富。它可能會比你做得更好。

關係數據庫並不真正用於存儲樹，但它們可以。我想不出任何特定的查詢問題，通過編寫一個定製的磁盤數據結構可以更好地解決問題。

Answer 2

編輯：這是用於內存映射文件的方法，我真的很喜歡你的直覺。我每次說「點」或「指針」時，我實際上是指從文件開始的零基偏移量。由於書面數據不會四處移動，因此節點的位置將作爲它們的全局標識符。

儘管節點不應該變大。我願意做它的方式是有節點如：

• 字符由節點持有（UTF-8編碼如果需要的話）
• 數組說，持有指向其子8個項目。這是用NULL（或0）靜態確定尺寸，不再指定更多的孩子。這個列表永遠不會變短，只會變得更大。
• 指向一段內存的指針，該內存包含另一個子指針數組，也是靜態標註的。即使你實際上不需要額外的空間，你也總是會這樣，你可以在其中寫入NULL。
  • 如果指向實際有效的內存，在列表之後，如果需要，您可以使用另一個指向額外列表的指針，這樣您就可以走到最遠。或者，第二個列表可以足夠大以容納所有字符。

作爲替代方案，靜態分配存儲器夠從一開始的所有字符。儘管這可能會變得太大，取決於樹的稀疏程度。

無論哪種方式，請注意這樣你的實際節點大小決不會增加，它有一個靜態長度。您可以根據需要在文件末尾添加額外的節點或額外的列表塊，並在開始時保留一個根指向所有子項的根目錄，這樣您就不必亂用頭部。