目标是建造非常大的树。非常大是指数亿个节点，适合几 GB。
问题是常见的数据结构有太多的开销。我买不起“节点”对象和子“地图”。我需要以非常紧凑的方式将其直接编码到内存中。
因此，我想知道是否存在一些具有整数作为键和值的树的内存高效实现，而不在内部使用对象，因此需要（键的 4 字节 + 值的 4 字节 + 子索引的 4 字节 + 免费的几个字节散列空间 = 平均每个条目 15 个字节）这将允许我使用外部映射 int<->keys 和 int<->values 来搜索树。
任何人？
PS：在内部使用对象至少要多使用 5 倍空间：8 个引用 + 4 个额外的哈希空间 + 16 个对象头 + 8 个键引用 + 8 个值引用 + 8 个父引用 + 8 个子引用 + (16 + x) 用于子映射 obj = 每个条目将近 76+x 个字节。（例如，我们的默认实现每个条目需要大约 100 个字节）
这实际上不是 Java 特定的问题，而是一个一般概念。
试试这个：http ://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html
关键是使用基元数组，以避免对象开销。
我不知道有什么特定的树实现可以做到这一点，但是 VTD-XML 在内部使用带有指向缓冲区的指针的令牌数组表示 XML 树（DOM）。也许您可以从他们的解决方案中得到启发？
I don't think you'll find anything already implemented for you, but what you've described could be very easily implemented using an IntBuffer. You'd create a "wrapper" class that converts indexes into records in the buffer, and instantiate/discard those wrappers as needed (ie, as you're traversing a tree, you probably don't care about holding a reference to the parent).
There are a couple of concerns:
TreeMap. But the algorithms are pretty simple, and available from Wikipedia.你可能会发现这个库可以帮助你实现你想要的——它是专门为将值存储为原语而设计的，并且在幕后做了一些字节码黑客操作，以产生存储对象的错觉。当...时使用它
...您希望在内存中有效地存储大量数据。该库可以显着减少 Full GC 时间并减少内存消耗。
它没有特定的 Tree 集合，但它可能会起作用，具体取决于您的需要。
每个节点都可以引用其父节点，而不是保留子节点列表。因此序列化一个节点不需要超过三个整数值（父、键、值）。
这种方法的一个问题是树遍历。获得所有节点子节点的明确列表将需要遍历所有节点。如果三元组按其父值排序，则可能会改进遍历。添加一个整数值，即指向下一个键的指针将允许将节点保持在链表中，从而简化节点的插入和删除工作。