Having a brain-freeze and looking for help with an algorithm

[amykhar]

I am working with a tree using the modified preorder tree.

http://www.sitepoint.com/article/hierarchical-data-database/2

What I am looking for is an efficient way to count things that are held in each node of the tree.

In other words, each node of the tree is a container. And each container has a number of things in it. I need to be able to count the things in such a way that the count of things in the parent nodes includes the number of things in the child nodes.

I know how to find all the child nodes. I know how to find the parent nodes. But, I am looking for an efficient way to query the database to get the count right.

Any thoughts?

[Marco van Herwaarden]

If you look at the bottom of the page you linked, you will see the forumla to calculate the number of children of a node.

[amykhar]

Yes. That's easy. My problem is I need to count the things that are inside each node. And, I need to have that count trickle up. So, if a parent has 1 thing in it and a node with 3 things in it, the parent would have 4 things in it. I would rather not do a query for each node if possible.

[Marco van Herwaarden]

You can do that calculation on each parent/node, no problem.

[amykhar]

I understand that I can do it with a query per node. I'm just wondering if I can reduce the number of queries. I would like to optimize it.

Amy

[Marco van Herwaarden]

SELECT *, (rgt - lft - 1) / 2 AS number_decendants
FROM tree
WHERE .....
Or perform the calculation in PHP.