Re: Storing a tree

On Mon, 12 Nov 2001, gravity wrote:

> On Thu, Nov 08, 2001 at 01:31:10PM +0100, Antonio Fiol Bonn?n wrote:
> > Hello,
> >
> > I have found a problem today to which I am unable to find the solution.
> > I write to this list looking for help.
>
> try this for something different:
>
> http://www.utdt.edu/~mig/sql-trees/

How I'm doing a tree structure in SQL is ... I'll just cut/paste my notes:

---
Fast SQL tree or hierarchy structure where you have varying levels of parent
and child relationships. Typical use include Internet portal category
listings, family tree, filesystem structure, or organization
classifications by company, division, and departments.

     TOP                     One big advantage of using this method is
      |                      you can search starting at any node andall
      +---O 01               it's branches or subnodes by using one query.
      |   |                  In addition getting the path by traversing
      |   +---O 0101         back to the top can be done with just one
      |   |   |              query instead of many recursive queries.
      |   |   +---O 010101
      |   |   |              The left diagram shows the relationship
      |   |   +---O 010102   between each node and their associated paths.
      |   |                  Here we are using 2 chars for each node. This
      |   +---O 0102         gives us a max of (using base 36) 36 * 36
      |                      immediate childs per node. Since SQL CHAR
      +---O 02               fields have a max of 255 chars, we can have
      |                      a max depth of 255 / 2 = 127. By varying the
      +---O 03               char width of each node, we can increase or
                             decrease the depth at the cost or value of
the number of child per depth. CHAR field type gives us the possibility of
using indexes on the column. If we for-go the indexes, we could use TEXT
fields for more depths and childs.

With this approach, you can easily move, delete any branch in that tree or
move it else where. Another interesting thing is given a node or path,
you can trace back all the way to the top using just one query. First
you'd break down the path by generations using substring (in PHP, Perl,
C) and select using the IN clause. For example:

Assume a table like:

CREATE SEQUENCE next_cat_id;

CREATE TABLE "categories" (
        "rec_id" int4 DEFAULT nextval('next_cat_id') PRIMARY KEY,
        "path" varchar(10) DEFAULT '' NOT NULL,
        "name" varchar(64) DEFAULT '' NOT NULL
);

Find the trail from current node to the TOP, we first break down the node

  Node 010102  => (01, 0101, 010102)

Then when you

  SELECT branch, name FROM tree
  WHERE branch IN (01, 0101, 010102)
  ORDER BY branch ASC

You'd get back results in order from the oldest parent to the youngest
child. Then pull the result as an array into your app and walk it to the
top to show the trail.

If you want to select all immediate child under a node:

  SELECT branch, name FROM tree
  WHERE branch IS LIKE '01__'

If you want to move a branch to another branch:

  UPDATE tree
  SET $pathField = ('$toPath' || ";
  SUBSTRING(path, CHARACTER_LENGTH('$fromPath') + 1))
  WHERE path LIKE '$fromPath%'"

To delete all the nodes under a branch '01':

  DELETE FROM tree WHERE path IS LIKE "01%"

Another nice thing is that you can seach for what ever, you can use the
" IS LIKE '$parentNode%' and search from that node to it's deepest child.

---