Creating tree-like structure (item, sub item, subsubitem) from a db?

[lfernando]

Hi there,

 

I think this is a big question but I'd appretiate any help you can provide!!

I have a list of items and subitems in a table that looks like this:

 

id  parent_id  title

1  0  House Chores

 

2  1  Take Out Trash

 

3  1  Clean Room

 

4  0  Grocery List

 

5  4  Eggs

 

6  4  Produce

 

7  6  Lettuce

 

8  6  Tomato

 

9  4  Milk

 

I want to display it like this:

 

(+) House Chores:

      > Take Out Trash

      > Clean Room

 

(+) Grocery List:

      > Eggs

      (+) Produce

            > Letutce

        > Tomato

      > Milk

 

 

So basically each entry in the table has an unique id and also a parent id if it's nested inside another item.

I "sort of" got it figured out in one way, but it doesnt really allow for nested subgroups. I'd like to know how would y'all PHP freaks to this

 

Also taking suggestions for the javascript code to expand/collapse the tree !! :)

 

Thank you!

[Adam]

Can the nesting be unlimited, or do you limit it to (up-to) 2 parent levels?

[lfernando]

I would like it to be unlimited. The way I did it now, it only allows for 2 levels, which is why I need your help 

[laffin]

Easiest answer: Recursion

 

some sample code

<?php
$db= array(
array(1,0,'House Chores'),
array(2,1,'Take Out Trash'),
array(3,1,'Clean Room'),
array(4,0,'Grocery List'),
array(5,4,'Eggs'),
array(6,4,'Produce'),
array(7,6,'Lettuce'),
array(8,6,'Tomato'),
array(9,4,'Milk')
);


function buildtree($node = null,$parent=0)
{
$arr=null;
        $idx=0;
foreach($node as $leaf)
{
	if($leaf[1]==$parent)
	{
		$arr[$idx][0]=$leaf[2];
		$arr[$idx++][1]=buildtree($node,$leaf[0]);
	}
}
return $arr;	
}

function showtree($node,$indent=0)
{
foreach($node as $val)
{
	echo str_pad(' ',$indent). (is_array($val[1])?'+':'>') . "{$val[0]}<br />\r\n";
	if(is_array($val[1]))
		showtree($val[1],$indent+2);
}
}

$tree=buildtree($db);

showtree($tree);

[ignace]

Easiest answer: RecursionClosure Table

[laffin]

Just read the article, and its a nice idea

However in a tree based system, storing all paths would be a nightmare to try and maintain.

Reason the recursion system is simpler and easier.

 

According to the article u wud need another table with the ancestor and descendant

so that table wud get rather huge when u are involving multiple paths as in the example given.

the seperate table also means that your queries will be a lot more complex as well as your coding, in order to maintain the referances.

 

Its an interesting article tho. But I don't see them as better than a simple recursion system.

 

House Chores ->  Grocery List

House Chores

House Chores -> Take Out Trash

House Chores  -> Clean Room

Grocery List

Grocery List -> Eggs

Grocery List -> Produce

Grocery List -> Produce -> Letutce

Grocery List -> Produce -> Tomato

Grocery List ->  Milk

 

 

[ignace]

In a Closure Table set-up you sacrifice disk space for performance. Using an Adjacency and sort it in memory is the wrong way of going at it certainly if you know their are structures available that allow you to get the entire tree with minimal effort correctly from MySQL.

[laffin]

Yes, like I said, EASIEST wud be the recursion system

the closure system is optimal in such a situation

 

but its implementation is also a lot harder to implement and maintain.

 

if u could provide a sample of the closure system using the same system above, u will soon realize that u have to write additional code for insertion, deletion, moving.

 

So the closure system although is optimal is performance, is not the easiest system to implement.

[ignace]

u will soon realize that u have to write additional code for insertion, deletion, moving

 

Apparently you aren't at all that familiar with Adjacency as the Closure Table is by design created to make these operations easier except insertion. It's true that at first your solution will work wonders until more and more users are starting to use your system, more and more chores are added/deeper nested and your easy recursion suddenly becomes a large bottleneck as your system now only sorts output instead of serving it.

[ignace]

Try it yourself:

 

1) create an average chore list (what do you need to do in a week/month/year?)

2) simulate a list for a 1000 other users

3) simulate these 1000 users actively using your website

4) notice how the load time increases as new users join and load/sort their chore list

[laffin]

Not so Ignace, as u see this recursion system already builds yer closure system on the fly,

so it wouldnt take much to convert the on the fly recursion system, into a closure system, by moving that array into a table for itself.

 

Yes, that recursion system is fast as easy to implement, as it is flexible to upgrade when u do have them 1000+ hits or more.

 

But if that recursion system is all thats needed, than there is is real need to beef it up.

 

 

Yeah, I gave it some thought about the recursion system that i use, and found the similarities with the closure system.

the biggest difference between the two is that one builds the referances on the fly, and the other stores em for subsequent access

 

[ignace]

Not so Ignace

 

For a news website that allowed it's users to comment on a comment (on a comment ..) the programmer before me used the Adjacency and a recursion function to sort those comments. 2 years later the website had lots of content, lots of comments and lots of users visiting the website daily resulting in a serious load (the analysis tool reported loads till 150%).

 

I completely re-wrote it to use the Closure Table design and load dropped to almost half. Sorting a big result in-memory is NOT a good idea and like you said Closure Table already stores the result sorted which should give you a clue about which design is optimal.

 

I'm not going to discuss this further if you believe Adjacency and Recursion is the way to-go then use it! At least you'll know what to choose when you ever come across the above scenario.