存储瓷砖数据超过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导致的访问模式。