If you need per-traversal state per node (such as visited status or intermediate dataflow), it's very handy to allocate another flat array for that and use the node indices.
I've looked into this in a compiler setting, transforming ASTs and intermediate representations.
[actualTreeNodeData1,child1Idx,child2Idx][actualTreeNodeData2,child1Idx,child2Idx][...]
instead of just [actualTreeNodeData1][actualTreeNodeData2][...]
Vary this to include whatever you actually need, could also be links to parents instead of or in addition to links to child nodes.Given we have indices along the serialisation for child nodes I would have thought not having nodes start at the consistent intervals doesn't hurt us for traversal at least.
I'd quite like to use this idea for a file backed immutable tree. The array of children would have variable size with bit field to index then nth child in the sparse array.
I suppose you could (should) write your own allocator to ensure nodes are allocated in a contiguous piece of memory, and have a separate array of indexes / pointers that tells you where the n-th node starts. That is another array that'll have to be kept in cache though.
This is super relevant to me right now, thanks!