存儲瓷磚數據超過1億個瓷磚每層多層

Question

問題：我正在嘗試爲我的地圖類存儲瓷磚數據。我有使用每層調色板的想法，調色板將描述層中的數據，該數據將是一個字節數組，每個字節代表一個瓦片類型。

這意味着1層1億個瓷磚將等於約96mb。但是我忽略了我可以在一個字節中實際存儲多少數據，事實證明，我當然只能存儲256個磁貼。導致256 *個瓷磚尺寸紋理尺寸的平方根（在這種情況下，256個瓷磚尺寸爲16）。 256 * 256紋理尺寸太小，因爲每個調色板只能有一個紋理。嚴重限制了我可以在一個圖層中的瓷磚。

我現在卡在一個綁定，就像我用2個字節（短）而不是1個字節來存儲瓦片數據，我會使我的內存使用量增加一倍，達到192mb每層。我至少想要4層。最終產品膨脹到768mb使用的RAM。我也無法描述數據中的數據，因爲每個字節的數組偏移量也是其位置的描述。

有沒有一種方法可以更有效地存儲這些數據。最壞的情況將涉及到我將所有這些保存到磁盤並緩存到磁盤的內存中。但我寧願保留在記憶中。

我想我可以在幾個小時內想出一些聰明的東西，但我想我會問，看看有沒有什麼常見的方法我不知道來解決這個問題。

Answer 1

我建議使用空間填充曲線（例如Hilbert curve）將數據表示爲映射到二維平面的數組。

然後，使用Huffman coding和run-length encoding的組合對其進行壓縮。如果您經常在本地重複數據（即存在大量彼此相鄰的所有片段），這將特別有效。

以256塊的方塊進行壓縮。然後，有一個偏移量數組，指示在某些字節數中壓縮數據的距離。

例如，第二塊的開始（瓦256）字節可以是在位置103，第三塊的起始（瓦512）可能是在192位置

然後說來訪問400塊，你可以算出這是來自第二塊，所以解壓第二塊（在這種情況下，從字節103到字節191），並從中得到400-256 = 144的塊。暫時保存（緩存）這個解壓縮的數據，很可能如果你得到附近的圖塊，他們也會在這個解壓縮的塊中。也許在你的偏移量數組中，你還應該包括最近緩存了哪些塊，以及它們在緩存中的位置。

如果您想允許修改，您可能必須將數據結構從一個大陣列更改爲一個向量向量。爲每個矢量都有一個指示符，不管它是否被壓縮。在進行修改時，解壓縮塊並對其進行修改，並在內存不足時重新壓縮最近最少修改的塊。

---

或者，你可以只轉儲整個結構到一個文件，memory map文件。這要簡單得多，但可能會更慢，這取決於數據的可壓縮性以及由於額外的I/O導致的訪問模式。