Lieven Cardoen

I will not go and explain the different ways of storing hierarchical data in a Database. This link provides some information on the topic together with a lot of other resources you can find on the internet. I’m using the preorder tree traversal algorithm. If you have more loading than writing to do, and you want to load the full tree very fast, the preorder tree traversal algorithm is ideal. However, if your tree gets very large (some 100.000 nodes in my case), then the preorder tree traversal algorithm isn’t that ideal anymore because it’s impossible to load the whole tree and send it to Flex (I must say we haven’t actually tried to do send the whole tree, but my guess is that Flex will either crash or get freezed for some minutes). We use lazy loading (if you load a Branch, only it’s children are also loaded, but not the children’s children). Loading however only the children of a branch is not easy with the preorder tree traversal algorithm. Or you need to do a self join or multiple sql queries.

Our implementation of the left right tree also has versions of nodes that it keeps. The consequence of this was that loading the children of a node took a couple of seconds. When a branch had for example 100 children, it could take up to 30 seconds, which of course is way too much. With some searching on indexes in SQL2005 a managed to reduce it to less than a second, which is really a great improvement.

This is a piece of the database design:

There are some other relations that I’ll leave away. The TreeStructures table holds the structure of different Trees (TreeId). The TreeNodes contain the data linked to a certain TreeStructure (branch, leaf). In this way, a TreeStructure can be linked to different TreeNodes, which in our case are versions. If a TreeNodes is edited and saved in Flex, then a new version is created. This means of course that when the children of a treestructure are queried, we also need to go and search for the latest treenode version of each treestructure child. Without an extra index, this is where everyting goes incredible slow. I’ve added a index on TreeStructureId (Table TreeNodes) and the result was wauwwwwww! Now it’s fun to work with the application in Flex. Saving a TreeNode should be a little bit slower now because SQL needs to update this extra index, but it’s so little that it can’t be noticed. And since saving a node from Flex is asynchronous, the user experience doesn’t suffer on it. Loading however has to go fast for a good usability!

In the future we will support different trees for a user. In this case the trees will not be as big as 100.000 branches and we could try sending the whole tree at once to Flex. Then we would have the full advantages of the preorder tree traversal algorithm.