Searching Infinite Sub Categories

[BrandonK]

For the longest time I've been working with a categorization system that only allows for 1 level of nesting (parent -> child_1), but now I have a requirement to add more. I can easily allow for an arbitrary number while knowing that the more levels of categories I add, the longer and more complex the SQL will be from extra joins, but I want to know if anyone has figured out a way to do infinite levels of nesting (parent -> child_1 -> child_2 [ -> child_n ]).

I can't fathom a way to do this (there are no loops or recursive functions in MySQL that I am aware of), but I thought I would ask before programming an arbitrary restriction into the system.

[longneck]

why yes, there is. http://www.sitepoint.com/article/hie...ata-database/2

[BrandonK]

Wow that's cool. Not the database schema I'm used to, but it looks really effective! I'll have to play around with it (specifically the rebuilding of the tree) before I make my mind up about it, but I can tell some guy thought long and hard about this problem once before

[longneck]

just so you know, inserting a leaf node is really easy. use left and right values that are +2 of the sibling to its left, and add 2 to the left and right values of all of the nodes with a left value larger than that same sibling.

[BrandonK]

Yeah, I saw that on page 3. I just want to play around with other irregularities of our category models. For instance, we have multiple trees. We have the main category tree that the users navigate through, but we also have internal categories. These are used for special groupings that aren't in the normal structure of site (such as sales and holiday gift guides). I haven't had a chance to play with it all yet, but I think I can include a "tree" column (where only 1 is public or something).

Looks like it'll be fun

[psalzmann]

While that article might be informative, it's plain complicated.

Do a search on google for a recursive category function. That's what you're after. 1 function to loop (and continue to loop through all nodes) until the last category is shown.

You'll need three main fields in your category table:

cid, parentid and level.

Level is good for when you make a pulldown menu and you want your pulldown values to look like:

Cat 1
--- Cat 2
------ Cat 3
Cat 4
Cat 5
--- Cat 6

As you can see, if you have that "level" in your db schema you'll be able to work with your "spacing" if you are writing pulldown menus as well.

From that category function I'm mentioning you'll be able to do a lot. You'll be able to generate single column views, double, tripple and 4-column views similar to ebay and their layout.

I guess it's just a matter of preference. Last year when I was looking around for nested category support in PHP I saw that article above. I wanted something fast, that didn't require too much thought at the time. This was complicated for me back then and I find my solution on google.

Search "nested category" or "PHP nested category function recursive". You'll find some great articles from PHPBuilder and other sites focusing on a more simplier approach to your problem

Peter

[r937]

peter, you consider a query within a loop within a loop within a loop ad nauseam to be fast???

brandon, you really do not want an "infinite" number of levels

in the real world, there will be some maximum number of levels, and even if this number seems large, it will not be infinite

think of your users, drilling down through those levels

at what point will a user say "da heck wid dis, i'm outta here" and go somewhere else?

have a look at this article: Categories and SUbcategories

even if you decide to have 15 levels (and i can assure you, that's still too many from a usability point of view), the sql is still very fast

[BrandonK]

I saw that post, and that's basically what I do with my categories now and its a schema that I am very familiar with. It works well and is easy to be understood by other developers that may edit my code.

That being said, I am looking at this new article with an open mind because it is very intriguing to me. I've never seen anything like it so I really just want to play with it and understand it. The biggest benefit I see from it is not speed (which is probably negligible from what you say in your article) or the ability to have infinite levels (like you said, that's way too many for what I'm going to use it for), but it is maintenance free (kinda). If I choose an arbitrary number, say 5, and build the site around that number, I know one day we'll push it to 6. If we change it to 6, I have to update SQL in a couple different spots and then edit my server side code to handle the extra fields returned too. Its not a show stopper, but maintenance free code is kinda nice.

On the other hand, it is much more complex to explain (I couldn't do it without a diagram), and the upkeep on the server is much more involved. Changing a node around can affect every node in the tree and require a couple hundred row changes. I still want to get some time to play with it today before deciding on anything, and I still welcome more input from the pros here.

[r937]

see Joe Celko's Trees and Hierarchies isbn 1-55860-920-2

[BrandonK]

I just got done reading his post on searchoracle.com and was thinking about looking for SQL for Smarties. I read that he devotes a couple chapters to hierarchal data storage. Do you recommend one over the other?

[r937]

yes, SQL For Smarties is the better choice, simply because there's so much more in it besides trees and hierarchies -- the chapter on nested sets is sufficiently comprehensive to let you know if you really want to use this data model

[BrandonK]

Thank you as always, Rudy and longneck (sorry, I don't know your first name).