Most efficient hierarchical product table

Question

I've built a few product databases but I'm never really satisfied with the effiency of the database. My best approach yet is to have one products table, one category table and then one relationship table ie:

Products table:

id    product_name     data
1     Some prod        More info...
2     Another prod     Even more...

Category table:

id    parent_id   cat_name
1     0           Main cat 1
2     1           Sub cat 1
3     1           Sub cat 2
4     3           Sub sub cat 1
5     0           Main cat 2

Relationship table:

id    prod_id    cat_id
1     1          2
2     1          4
3     2          5
etcetera...

This makes it fast and easy to retrieve the products and also easy to have one product assigned to more than one category.

However the structure for creating the category listing is not as simple as I'd like. First I need to loop the main category, then all the sublevels accordingly. I only like to show categories that has products assigned, but then of course I also need to show all the parent categories if a sublevel contains products. This results in plenty of queries, joins and conditional routines to present the current categories. I wonder if there might be a more efficient structural approach to this problem? You don't need to write my code I just wonder what kind of better principle there might be?

MySQL doesn't support recursive functions, so it is not well suited to this adjacency list model of storing hierarchical data. You ought to consider restructuring your data to use either nested sets or closure tables. See [this answer](http://stackoverflow.com/a/192462/623041) for more information. — eggyal, Sep 10 '12 at 08:08
@eggyal as a side-note aren't recursive functions supported but with a fixed recursion depth (which is by default set to 0)? — Mihai Stancu, Sep 10 '12 at 08:11
Or you could use a database platform which does support `WITH` and hierarchical structures. — podiluska, Sep 10 '12 at 08:11
See this article for nested tree : http://www.sitepoint.com/hierarchical-data-database/ (start at page 2) — grunk, Sep 10 '12 at 08:13
@MihaiStancu: You're right that *stored procedures* are limited to recursion of up to [`max_sp_recursion_depth`](http://dev.mysql.com/doc/en/server-system-variables.html#sysvar_max_sp_recursion_depth`) (default of zero), but *stored functions* cannot be recursive under any circumstances. In this case, one would really want to use a function in queries like `WHERE is_descendent(node.id, 46)`. — eggyal, Sep 10 '12 at 08:17
@podiluska Thanks but i'm probably stuck with MySQL because of many things. — jtheman, Sep 10 '12 at 08:21
@grunk I've read this article about the "Modified Preorder Tree Traversal" metod. It seem quite good but a little hard to understand, I will try to dig a bit deeper... — jtheman, Sep 10 '12 at 08:40
@jtheman in case you haven't figured it out yet MPTT is the more appropriate scientific name for nested sets. — Mihai Stancu, Sep 10 '12 at 09:57

Mihai Stancu · Accepted Answer · 2012-09-10T08:22:32.677

2

The typical recursive approaches are the adjacency tables and the many-to-many tables.

The typical non-recursive approaches are many-to-many ancestor tables and nested sets.

Adjancency lists are those structures that contain a "parent_id" reference.

Many-to-many tables being read recursively are your approach.

Ancestor tables are many-to-many tables but they also contain child-grandfather connections and specify the level of each connection. They allow the most flexibility and the fastest read/write speed.

Nested sets are a very different approach, they only allow strict tree structures not graphs. They are also more costly on writes but very easy on reads.

Also regarding nested sets, maintaining the structures manually is pretty hard. And you need to implement several functions and choose when to use each, because inserting a node at the end of the child-list needs one function (appendNodeTo($parentNode)) while inserting a node at the middle of the child-list needs another. Moving nodes around depends on weather the node is a terminal nod (a leaf) or if it has subnodes (a branch) with specific functions for that too.

edited Sep 10 '12 at 08:22

answered Sep 10 '12 at 08:10

Mihai Stancu

15,848
2
33
51

Do I get this correct that the recursive approach is very efficient in retrieving from the database but slower on inserts? (this is quite good...) – jtheman Sep 10 '12 at 08:15
1

I've updated my answer with some specifications. Yes, the structure makes it difficult to update/insert, it need you to re-wire half of the ancestor nods in the tree for one update. – Mihai Stancu Sep 10 '12 at 08:19
Thanks. I'm considering the nested set approach as it is tempting to get the data out easy. But as you suggest the downside is of course that I will need to code an automated routine to insert/update items in the category listing. As I'm constructing a CMS for this it will of course be needed. – jtheman Sep 10 '12 at 08:26
I'm setting this to be my accepted answer, as I'll go for the nested tree method. But thanks also to all that commented and other answer. – jtheman Sep 10 '12 at 09:55

score 1 · Answer 2 · answered Sep 10 '12 at 08:14

this is not the most efficient way but this way you only need 1 sql request(query)

 public function get_menu_data()
    {
        $result = mysql_query(" 
            SELECT 
                id, parent, name 
            FROM 
                category 
            ORDER BY 
                parent, name 
        "); 
        //$cat = $this->db->get("category");
        $menuData = array( 
            'items' => array(), 
            'parents' => array() 
        ); 

        while ($menuItem = mysql_fetch_assoc($result)) 
        { 
           $menuData['items'][$menuItem['id']] = $menuItem; 
           $menuData['parents'][$menuItem['parent']][] = $menuItem['id']; 
        } 
        return $menuData;

    }

function buildMenu($parentId, $menuData)
{
    $html = '';
    if (isset($menuData['parents'][$parentId]))
    {
        $html = '<ul>';
        foreach ($menuData['parents'][$parentId] as $itemId)
        {
            $html .= '<li>' . $menuData['items'][$itemId]['name'];
            // find childitems recursively
            $html .= $this -> buildMenu($itemId, $menuData);
            $html .= '</li>';
        }
        $html .= '</ul>';
    }
    return $html;
}

call it like: show all categories:

buildMenu(0,get_menu_data());

show sub categories of categorie 1:

buildMenu(1,get_menu_data());

good luck and i hope this code helps you

Thanks. Hovewer I also need to query the DB for checking if products exist in each category and only show it depending on IF each category OR its child levels contain a product. — jtheman, Sep 10 '12 at 08:19

Most efficient hierarchical product table

2 Answers2