My $.02 on Storing Trees

(epsilondelta posted about storing trees in a database, here’s my thoughts)

It occurs to me that Pr�fer coding doesn’t seem optimal for trees that change often. As it stands now, the data structure is a single table with each tree as a unique identifier and each node a unique identifier, and each tree carries with it a Prüfer code.

Every time a node is added or removed from the tree, the tree’s code could be altered (depending on the label of the edited node, any position may be changed)

1. Take the following tree for example. It has Prüfer code 4445 and can be stored accordingly.
   
2. Removing node 2 from it results in its code changing to 445.
   
3. But, if we add a node instead, we get 44545:
   

Thus, any time a change is made to the tree, the entire tree must be recreated in the database, which will be expensive.

I would suggest that a second table be introduced in which the Prüfer code could be stored separately from the nodes of a given tree so that adding or removing a node requires that you only update the stored code and INSERT or DELETE a single record. The entire tree could be retrieved using a single query such as SELECT n.data, n.label, t.code FROM tree_nodes n, tree_codes t WHERE t.id = n.treeid.