Re: Tree structures in an RDBMS

>> The often quoted Joe Celko's left-right indexed tree example
disqualifies for my purposes, since the tree itself is far from being static - it is steady growing and even reordering from time to time (as stated in the requirements) <<

You might want to try my nested sets model. The gimmick is that you have to have one table for the tree structure (i.e. the organizational chart) and another for the nodes (i.e. the personnel who hold positions in the organization). Because each tree structure is only three integers, you get a lot of data on a physical data page and in cache. For example, a 16 Kbyte datapage is about 2700 nodes, times the size of your cache -- 10 pages? 100 pages?

I am working on some algorithms to swap siblings, compare subtrees for the same structure, etc. Right now, adding a youngest sibling (i.e rightmost) is easy:

BEGIN
DECLARE right_most_sibling INTEGER;

• this can be put into the update and make one statement SET right_most_sibling
  • (SELECT rgt FROM Personnel WHERE emp = :your_boss);

UPDATE Personnel

   SET lft = CASE WHEN lft > right_most_sibling

                  THEN lft + 2
                  ELSE lft END,
       rgt = CASE WHEN rgt >= right_most_sibling
                  THEN rgt + 2
                  ELSE rgt END

INSERT INTO Personnel (emp, lft, rgt)
VALUES ('New Guy', right_most_sibling, (right_most_sibling + 1)) END; This generalizes to the insertion of a whole subtree.

I don't know what your problem is, but I hope this helps. Received on Thu Nov 29 2001 - 23:54:03 CET