blocks|key|667751|text|这实际上不是Java特有的问题，而是一个更一般的概念。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|667752|试试这个：http://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html|offset|length|667753|关键是使用基元数组，以避免对象开销。|667754|entityMap|0|LINK|mutability|MUTABLE|url|http://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html^0|0|5|1N|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@$D|R|E|S|1|T]]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

That's actually not a Java specific question but more of a general concept.

Try this: <a href="http://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html" rel="nofollow">http://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html</a>

The key would be to use arrays of primitives, in order to avoid object overhead.

blocks|key|676149|text|我不知道有什么具体的树实现可以做到这一点，但VTD-XML在内部使用带有指向缓冲区的指针的标记数组在内部表示XML树(+DOM)。也许你可以从他们的解决方案中获得灵感？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|676150|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I don't know of any specific tree implementation that does exactly that, but VTD-XML represents an XML tree (the DOM) internally using an array of tokens with pointers into a buffer. Perhaps you can get inspired by their solution?

blocks|key|3930620|text|你可能会发现这个库可以帮助你达到你想要的效果--它是专门为将值存储为原语而设计的，并且在幕后做了一些字节码的破解，给人一种存储对象的错觉。在以下情况下使用它：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3930621|3930622|+...您希望在内存中高效地存储大型数据集合。这个库可以极大地减少完整的GC时间，并减少内存消耗。|blockquote|3930623|3930624|3930625|它没有特定的Tree集合，但它可能会做到这一点，这取决于您需要什么。|3930626|http://code.google.com/p/vanilla-java/wiki/HugeCollections|offset|length|3930627|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|0|0|0|0|0|1M|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|V|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|W|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|X|8|@]|9|@]|A|$]]|$1|G|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|Z|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|10|8|@]|9|@$L|11|M|12|1|13]]|A|$]]|$1|N|3|-4|5|6|7|14|8|@]|9|@]|A|$]]]|O|$P|$5|Q|R|S|A|$T|K]]]]

You may find that this library helps you achieve what you want - it is specifically designed for storing values as primitives and does some bytecode hackery behind the scenes to give the illusion of storing Objects. Use it when...

<blockquote>
 ... you want to efficiently store large collections of data in memory. This library can dramatically reduce Full GC times and reduce memory consumption as well. 
</blockquote>

It doesn't have a specific Tree collection, but it might do the trick, depending on what you need.

<a href="http://code.google.com/p/vanilla-java/wiki/HugeCollections" rel="nofollow">http://code.google.com/p/vanilla-java/wiki/HugeCollections</a>

blocks|key|3930657|text|我不认为您会发现已经为您实现了什么，但是您所描述的内容可以很容易地使用IntBuffer来实现。您将创建一个“包装器”类，将索引转换为缓冲区中的记录，并根据需要实例化/丢弃这些包装器(即，当您遍历树时，您可能并不关心是否保留对父对象的引用)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3930658|这里有几个问题：|3930659|包装器实例的|3930660|垃圾回收:只要它们是短暂的，它们就永远不会离开伊甸园，所以GC几乎是免费的。|unordered-list-item|3930661|在缓冲区内对记录进行垃圾回收:如果你有一次写入树，这是没有问题的。否则，您将需要维护一个空闲列表。不难，但需要一些时间。|3930662|实现树的一般机制:像TreeMap这样的类已经为你完成了。但是算法非常简单，可以从Wikipedia.|style|CODE|3930663|获得|3930664|entityMap|0|LINK|mutability|MUTABLE|url|http://download.oracle.com/javase/6/docs/api/java/nio/IntBuffer.html|1|http://en.wikipedia.org/wiki/Red-black_tree^0|Z|9|0|0|0|0|0|0|A|7|15|9|1|0|0^^$0|@$1|2|3|4|5|6|7|12|8|@]|9|@$A|13|B|14|1|15]]|C|$]]|$1|D|3|E|5|6|7|16|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|17|8|@]|9|@]|C|$]]|$1|H|3|I|5|J|7|18|8|@]|9|@]|C|$]]|$1|K|3|L|5|J|7|19|8|@]|9|@]|C|$]]|$1|M|3|N|5|J|7|1A|8|@$A|1B|B|1C|O|P]]|9|@$A|1D|B|1E|1|1F]]|C|$]]|$1|Q|3|R|5|6|7|1G|8|@]|9|@]|C|$]]|$1|S|3|-4|5|6|7|1H|8|@]|9|@]|C|$]]]|T|$U|$5|V|W|X|C|$Y|Z]]|10|$5|V|W|X|C|$Y|11]]]]

I don't think you'll find anything already implemented for you, but what you've described could be very easily implemented using an <a href="http://download.oracle.com/javase/6/docs/api/java/nio/IntBuffer.html" rel="nofollow">IntBuffer</a>. 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:

<ul>
<li>Garbage collection of the wrapper instances: as long as they're short-lived, they never get out of Eden, so GC is almost free.</li>
<li>Garbage collection of records within the buffer: if you have a write-once tree, this is no problem. Otherwise, you'll need to maintain a free list. Not difficult, but it takes some time.</li>
<li>General mechanics of implementing a tree: this is already done for you with classes like <code>TreeMap</code>. But the algorithms are pretty simple, and available from <a href="http://en.wikipedia.org/wiki/Red-black_tree" rel="nofollow">Wikipedia</a>.</li>
</ul>

blocks|key|667747|text|每个节点都可以有一个对其父节点的引用，而不是保留子节点的列表。因此，序列化一个节点不需要超过三个整数值(parent、key、value)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|667748|这种方法的一个问题是树的遍历。要获得所有节点子节点的确定列表，需要遍历所有节点。如果tripplettes根据它们的父值进行排序，则遍历可能会得到改进。再增加一个整数值，即指向下一个键的指针，将允许将节点保留在链表中，从而减轻了插入和移除节点的工作。|667749|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Instead of keeping a list of children, every node could have a reference to its parent. Thus serializing a node wouldn't need more than three integer values (parent, key, value).

A problem with this approach is tree traversal. Obtaining a definite list of all node children would require iterating through all nodes. If the tripplettes are sorted by their parent values traversal may be improved. Adding one more integer value, i.e. a pointer to the next key would allow keeping the nodes in a linked list easing the job of insertion and removal of nodes.

The objective is to build very large trees.
By very large I mean hundreds of millions of nodes, fitting in a few gigabytes.

The issue is that common data structures have way too much overhead. I cannot afford to have "node" objects and children "maps". I need to directly encode it into memory in a very compact way. 

Therefore, I was wondering if there existed some memory efficient implementation of trees having integers as key and values, without using objects internally, therefore needing (4 byte for key + 4 bytes for value + 4 bytes for children index + a few bytes for free hashing space = 15 bytes per entry on average) which would allow me to use an external mapping int&lt;->keys and int&lt;->values to search the tree.

Anyone?

PS: Using objects internally uses at least 5 times more space: 8 reference + 4 extra hash space + 16 object header + 8 key ref + 8 value ref + 8 parent ref + 8 children ref + (16 + x) for children map obj = nearly 76+x bytes per entry. (for instance, our default implementation needed around 100 bytes per entry)

java: very large trees?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

目标是建造非常大的树。我说的非常大，指的是几亿个节点，只有几个千兆字节。问题是普通的数据结构有太多的开销。我不能拥有"node“对象和子”map“。我需要以非常紧凑的方式将其直接编码到内存中。因此，我想知道是否有一些将整数作为键和值的树的内存高效实现，而不在内部使用对象，因此需要(4字节的键+4字节的值+4字节的子索引+几个字节的空闲散列空间=每个条目平均15个字节)，这将允许我使用外部映射int

问java:非常大的树？
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问java:非常大的树？EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问java:非常大的树？
EN