What is fast, compact representation of tree structures that prevents cache misses?

Question

Graphical applications often represent images as flat arrays, instead of bidimensional arrays. If I'm not mistaken, this is done because flat arrays are much faster as they're compact and avoid cache misses. Example:

dimensional_array = [[1,2],[3,4],[4,5]]
four = dimensional_array[1,1]

flat_array = [1,2,3,4,5,6]
four = flat_array[1 + 2*1]

Is there a similar (or not) representation of free-form trees that allows for the same kind of performance gain?

free_form_tree = [[1,2,3],4,5,[[6,7],8]]

Answer 1

If your tree is fairly complete (or you don't care as much about wasting space) and can fit into memory then you can store the tree in an array. You can use the same formula that an array based heap uses to "search" the tree.

• root is at index 0
• Children are always at indices (2*i + 1) and (2*i + 2) where i is your current index.
• Their parent is floor((i − 1) ∕ 2) where i is a child's index.

Storing binary tree as an array.

Also, see heap details here.