Ask HN: How to traverse a transitive closure tree in preorder?
1 comments
Well, the best idea I can come up with that stays in line with the idea of transitive closure trees being fast to query is to keep the preorder as an integer on the data table.
This method means moving all those integers up when we insert somewhere in the middle of the preorder, but ah well, at least that process comes during the not so common write instead of read.
This method means moving all those integers up when we insert somewhere in the middle of the preorder, but ah well, at least that process comes during the not so common write instead of read.
I'm working on a transitive closure tree implementation. I seem to have managed to implement everything else I need except a way to traverse the tree in preorder.
I've been using http://www.slideshare.net/billkarwin/sql-antipatterns-strike-back from page 68 as a reference for the build.
Currently I use depth to order the descendant call, which gives me a very quick level order result.
Anyone got any idea how to run a preorder traversal on this type of data structure?