One of the issues I ran into while building a scenegraph like that was the pure index-based approach works great for static graphs such as a skeleton mesh but becomes a headache for dynamic graphs
I ended up building a graph structure ontop of the ID/indirection container Sean suggested here (http://gamedev.stackexchange.com/questions/33888/what-is-the-most-efficient-container-to-store-dynamic-game-objects-in) but perhaps there's a better way to do it.
Something i've done before is that each object (typically static in its own design) is its own data-oriented array, but that array could be parented to any particular index in another object's data-oriented array. This allowed for the transform code to be parallelized by objects based on a very simple dependency model.
I took it a step further so that each bone in the array could be parented to a different bone in the parents objects array, but limited to having one parent array. That kept the dependency model simple but with enough flexibility to do for example, skinning-only transforms by having every bone in a skeleton parented to the matching bone in the animated skeleton.
EDIT: This also allowed for each of the flat arrays to be inserted into an acceleration structure under a single spatial hash, instead of having to test each node within it.