構建並導出內存有限的非常大的樹形結構

總而言之，我有一個應用程序，它接收一組輸入文件，從數據生成一個樹，然後將其作爲XML寫入文本文件。構建並導出內存有限的非常大的樹形結構

目前，整個樹在寫出之前就被存儲在內存中，因爲在解析過程中，我們需要引用樹上的任意節點來獲取或更新其值。

當樹變得太大而無法將其全部存儲在內存中時，就會出現我們面臨的問題。樹本身非常平坦，只有4-6層的深度。它看起來是這樣的

Root 
    Group 
     Record 
     Data 
     Data 
     Record 
     Data 
     Data 
     Data 
     ... 
     ... 
    Group 
     Record 
     ...

總是會有一個Root節點，每個節點只有一個類型的孩子。但是，對節點添加到其他節點的方式沒有任何順序：根據數據的格式化方式，可以將記錄添加到不同的組，並且可以將數據添加到不同的記錄（而不是爲一個記錄創建一個記錄組，然後移動到另一個）

我的第一個建議是在我們的機器上丟掉更多的內存。我們在64位Windows機器上運行該工具，所以如果我們內存不足，那麼我們只需要獲得更多內存。但是這個建議沒有采取。

我接下來的想法是每當樹佔用內存空間太多時寫出節點，但因爲可以隨時將數據添加到特定記錄，因此很難確定實際完成時間有記錄或沒有記錄。特別是如果我們需要引用記錄，並且它已經被寫出。

還有其他幾個選項，例如優化樹的設計方式（因爲每個節點佔用相當大的內存），但是對於這個問題，我想知道構建和導出大型樹的技巧。

來源

2013-11-20 MxyL

如果它太大而不適合內存，爲什麼要將它輸出到單個XML文件？這本質上並不是一個壞的方法，但它看起來似乎是錯誤的工具。 –

如果我是你，我會在處理它時堅持樹，而不是將它存儲在內存中。通過持久性，我的意思是從平面文本文件到關係數據庫再到面向圖形的NoSQL解決方案。

然後，您可以創建一個基於Java bean的基本訪問層，以執行您需要執行的CRUD操作，然後在這裏繼續。

另一種選擇是動態構建XML文件，從而跳過內存樹的構建。爲此，您可以利用SAX（基於事件的XML處理解決方案），而不是將整個文檔加載到內存中。

來源

2013-11-20 20:15:21

在我看來，有兩種方法可以解決這個問題。

瞭解有關數據用法的更多信息以確定特定模式，併爲您的用例提出最有效的方法。
將數據視爲黑盒子，假設任何訪問或更改數據的場景都可能具有相同的頻率和概率。

你沒有給我們任何食物的第一種方法，所以我們必須承擔後者。高速緩存的概念是一個解決方案。有不同類型的緩存，但基本概念是，儘可能多地保留在內存中，一旦超過了某個限制，就會持續存儲和刪除使用次數最少或時間最長的部分。

當你這樣做時，你可以選擇將實際的樹結構保留在內存中，只清除節點內容或清除節點內容和樹結構本身。如果您的節點數量很大但數量有限，那麼如果保持樹狀結構使「清除」節點儘可能輕量化，則可能會更好。但是，如果樹中的節點數量實際上是無限的，那麼您可以考慮清除整個子樹。

對於通常通過訪問子樹完成樹訪問而非完全隨機訪問的用例，最後一種方法可能非常有效。

如果您提供有關數據和使用模式的更多信息，我們可能會提出更詳細的建議。

來源

2013-11-20 20:21:37 ATrubka

1）我想到的第一個選項是將所有（父子）對存儲在數據庫中，然後遞歸地探索它以從中構建XML。

2）另一種方法是通過掃描整個輸入三次（每一層掃描一次，以父記錄開始，以root結尾），自下而上進行。每個圖層都作爲一組XML文件存儲在磁盤中，每個節點一個。然後，在樹中構建更高級別時，可以將子文件簡單地附加到其相應的父文件（因爲它們保證完全填充）。這需要維護2個內存中索引;一個用於當前級別，另一個用於下一級別。這些索引指向文件。

來源

2013-11-20 20:27:39

在磁盤上創建一個工作目錄。
通讀數據。當你遇到一個你以前沒有見過的組時，在工作目錄中爲它創建一個子目錄。當您看到之前沒有見過的記錄時，請在相應的組目錄中爲其創建一個文件。當你看到一些數據時，將它附加到適當的文件中。繼續閱讀，直到完成對數據的閱讀。
步行文件樹，並將記錄文件的內容連接到輸出文件，並使用相應的根和組標記。
刪除工作目錄，一切都在它

如果你掛在內存中的文件句柄，並重新使用它們寫入和讀取階段之間（這意味着使用一個RandomAccessFile或MappedByteBuffer ，你可以同時寫和讀，倒帶），並且不會在任何時候刷新它們，那麼你將把磁盤IO和緩存的問題完全交給操作系統（好吧，運行時庫等等）。如果操作系統決定程序執行的最佳方式是將一些數據寫入磁盤，它就會這樣做。如果它可以全部適合內存，它會將它全部保存在內存中。它將能夠批量寫入，因此它們很好，很大，因而高效。它將能夠預讀取讀取，這是對一組文件的順序遍歷，因此可以預測。如果你的操作系統是好的，那麼這個問題就像這個問題所承認的那樣是一個有效的解決方案。如果是Windows，它可能不是。

另一個竅門是將數據寫入非XML文件，但採用更緊湊的中間格式，只將其轉換爲XML作爲最終輸出。這將更有效地使用緩存和帶寬。

來源

2013-11-20 22:06:10

構建並導出內存有限的非常大的樹形結構

回答

相關問題