For a numerical simulation framework, I use a hierarchical Cartesian grid in 3D to discretize the computational domain. I am thus looking for the most space-efficient way to store the resulting octree on disk, given the following conditions:
- It is very sparse (i.e., not all nodes exist), but potentially deep (a depth of 20 or beyond)
- It is stored depth-first (pre-order)
- All parent nodes up to the root node must be stored (i.e., it is not sufficient to store just the leave nodes)
- The amount of data per node is a global constant
The best I can come up with is
6 7 bits per node: 3 bits to indicate the position of a node with respect to its parent, and 3 4 bits to store how many child nodes exist. However, intuition tells me there should be a more efficient way. Please note that algorithmic efficiency is not part of the question, as its representation in memory will be different anyways.
P.S.: Please let me know if CS is not the right SE venue for this kind of question.
The resulting data structure will be stored in a file on disk, thus the need for an efficient encoding of the octree. There are additional data files that contain information associated with each existing node (e.g., solution data). To have a one-to-one relationship between nodes ("cells") in the octree file and the datasets, it is required to store all internal nodes (i.e., non-leaf nodes) in the octree file as well.
An octree with 5 nodes: 0, 1, ..., 4. Their relationship is the following:
- 0 is the root
- 1 is child 0 of node 0
- 2 is child 1 of node 1
- 3 is child 5 of node 1
- 4 is child 1 of node 0
The resulting tree would look something like this (with missing nodes omitted)
and the nodes need to be stored
0 1 2 3 4 (pre-order depth-first).