EllisLab text mark
Advanced Search
     
Nested lists with infinite depth
Posted: 05 February 2010 06:06 PM
Avatar
Joined: 2008-01-03
728 posts

How do you handle them?

Let me give an easy example to explain what I’m talking about:

Table ‘categories’ with the following fields:
- id
- name
- parent_category_id

As you can see, we have a simple parent-child relationship where for the top categories the parent_category_id is empty for every other lower category it contains the id of the parent category.

Now in theory the resulting tree/nested list can have an infinite depth which makes things harder compared to having a limited depth.

While working on this I came up with 2 possible solutions:
1. Select all top level categories (where parent_category_id is null) and then for each of them select the child categories and then for each of the child categories select their children and so on, could be done pretty easily using recursion but you might end up with many queries resulting in a slow application.
2. Select all categories at once and then use recursion to bring them into a hierarchical structure, e.g. in a multi-dimensional array.

I ended up using the 2. solution as I wanted to keep database usage to a minimum.

So, how would you guys have solved this? Is there a 3. way to do this? Did I miss something entirely?

Tell me what you think.

P.S.: I gotta talk about this with the client this project is for, but maybe I can release the functions I used as a CI helper.

waldmeister

 Signature 

Blog - Twitter

DBlog

MeNeedz: Auth - Cloud - Password - Search - Shoutbox - Akismet -
Twitter - Visitor tracking

 
Posted: 05 February 2010 09:26 PM   [ # 1 ]   [ Rating: 0 ]
Avatar
Joined: 2008-07-20
262 posts

I had to do the same thing for a work project where there was unlimited nesting of categories, so you could have a parent of a parent of a parent etc. I ended up using the same solution as yourself #2. It’s the most efficient way to do this. Most of the time the database will be the slowest part of your application, so doing 1 call rater than multiple will be quicker, the function to change the flat structure into a tree isn’t very long or processor heavy either.

I don’t have my helper with me here (it’s at work) but it’s not overly complex. You can create a simple function using the PHP example here ==> http://www.tommylacroix.com/2008/09/10/php-design-pattern-building-a-tree/.

 Signature 

I heard that big fonts are in this summer? All the cool kids seem to be doing it!  | Mario Visic - Freelance Web Programmer | HumorList - It’s got stripes!