use Perl

• Finding subtrees (Score:1)

  by dws (341) on 2003.03.31 20:31 (#18578) Homepage Journal

  If you have a static tree (i.e., no inserts or infrequent, scheduled inserts), there's a trick from one of Joe Celko's SQL books that might apply. (From memory...) Walk the tree using a linear sequence generator that starts at 1. As each node is reached pre-order, store (insert/update) the next id that well be generated. The next id represents the "left" side of the subtree rooted under each non-terminal node. As the node is reached post-order, assign (update) its id from the sequence generator. When you do this, the root id can be found via

  SELECT COUNT(*) FROM tree

  or

  SELECT MAX(id) FROM tree

  and the entire subtree under a node can be selected by

  SELECT * FROM tree WHERE id >= ? AND id < ?

  where the values you plug in are the "first id in subtree' value cached in the parent node and the node id of the parent.

  This scheme works wonderfully when you have static data, or data that you can update (and re-walk) on a scheduled basis, but fails miserably if the table needs to be updated live.

  Reply to This

  • Re:Finding subtrees (Score:2)

    by gnat (29)

    You're the second person to recommend a Celko book. Hi ho, hi ho, it's off to Amazon I go ... :-)

    Thanks!

    --Nat