Tree Database

any database preferablt mysql....

yes, but I've to admit that postgresql is more powerful and faster

I whant to know how with tabe can I make Tree stucture

I whant to know how with table can I make Tree stucture

that's an other question, isn't it ? :D

let's try to be gentle to you :

basically a tree (folder tree or other) is a structure in which elements have parents (links to other elements) and children (ditto).

Do you know how many leaves/children you may have per node/element ? 2 is for a binary tree, 3 for a ternary one, etc

Let's suppose you provide up to 5 leaves per node.

Then the DB structure would ressemble this :

CREATE DATABASE mytree;
USE mytree;
CREATE TABLE firstree(id integer unique auto_increment,name char(10),parent integer,child1 integer default 0,child2 integer default 0,child3 integer default 0,child4 integer default 0,child5 integer default 0);
# now create some sample and simple tree
INSERT INTO firstree VALUES (0,'root',0,1,2,0,0,0);
INSERT INTO firstree VALUES (0,'first child',1,0,0,0,0,0);
INSERT INTO firstree VALUES (0,'second child',1,0,0,0,0,0);
# you now have a tree of three nodes all linked together
# to add a child to an element ID1, search for a 0 in its children (child1,2,3,4,5), insert the new element with parent=ID1 and no children (set to 0 as above), get its id ID2, then modify the parent ID1 so that childrenX=ID2
# to display the tree, start with the (unique) element having parent=0 : it's the root of the tree
# then memorize its children in sequence
# then display their names horizontally while memorizing their children
# repeat until no children memorized to display. (this is naturally recursive and should be done that way, in PHP for example)

I think my answer is worth the points 8-)

Yuck.  Not very foward thinking of you VGR, IMHO.  What if more children are needed later on?

Look, you don't need to specify who the children are in you table.  You table structure simply needs to look like this:

  create table tree(
        id int primary key not null,
    parent int references(id) null
  );

Put whatever else you need in the table per your needs.  Any nodes in the tree that are on the root level will have parent set to NULL.  Otherwise, the parent will be set to the node's parent id.

insert into tree(parent) values (NULL);
insert into tree(parent) values (NULL);
insert into tree(parent) values (1);
insert into tree(parent) values (2);
insert into tree(parent) values (3);

This would result in a tree that looks like:

1 -
  3 -
    5
2 -
  4

Sorry if the above spacing doesn't come out.  Basically, you'll have node 3 a child of node 1 and node 5 a child of node 3, node 4 a child of node 2.

In order to traverse the tree, you would use a recursive function.  Or, if you're blessed with PostgreSQL, you can just write a recursive stored procedure or whatever.


If you really want to specify who the children are, then you'll need a seperate table that map children nodes to parent:

  create table childMapping (
          id int primary key not null,
     tree_id int,
    child_id int
  );

But this is really not necessary because you can always find out who the children of a certain node are by simply:

  select * from tree where parent = $id;

not very pragmatic thinking of you bobsledbob , IMHO

you've to check the DB to have the children of an element...

Leave the academic "minimal" definition (I know it), and accept that IN PRACTICE, 5 children is more than enough for a lot of applications.

A sexary balanced tree I'm still waiting to see.

Doing the "joint table" childMapping is also what I would have suiggested if the maximum number of leaves par node was unknown and potentially big. BUT it's INEFFICIENT to stay polite.

My suggestion to the Asker is : do whatever suits your needs the more closely, and think "database space" and "efficiency, time to compute" too :D

agree with you VGR, my method is potentially not as efficient, but that would depend on the database and the requirements of the application.

my technique for a large tree in MySQL for instance would require an enormous amount of select statements to say traverse the tree from top to bottom.

however, with a real database like PostgreSQL, it would be trivial to write a very fast recursive select statement that would perform just as fast as the required statements to traverse your tree.

for a fairly flat tree or small tree (like a small file system or a website sitemap), my definition works pretty good.  For a fairly deep or large tree, contraining the definition like you've got is probably better.

I think your advice is very correct, 'do whatever suits your needs...'  Ultimately, this type of decision is contingent on what your specific needs are and what you've got to work with resource wise (db, etc.).

yes, and in this case the Asker has said "like a folders tree", so I suppose there will be a lot of leaves per node and no known maximum, so my solution is worse than yours (more general).

No comment has been added to this question in more than 21 days, so it is now classified as abandoned.

I will leave the following recommendation for this question in the Cleanup topic area:
    PAQ - no points refunded

Any objections should be posted here in the next 4 days. After that time, the question will be closed.

snoyes_jw
EE Cleanup Volunteer