java: very large trees?

Question

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<->keys and int<->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)

Answer 1

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

Try this: http://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html

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

Answer 2

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?