Formatting a multi-level menu using only one query

By crisp on Sunday 23 December 2007 23:46 - Comments (22)
Category: PHP, Views: 43.346

In the programming forum (dutch) on Gathering of Tweakers I often see people struggeling with multi-level menu's stored in a database and the formatting of such menu in HTML.

This is actually quite a common programming problem that can be solved using some kind of recursion or stack-based processing in order to create a tree out of a flat datastructure containing parent-child relations. However, in most cases the final solution that is presented involves seperate queries being executed inside a loop or inside a function that is called recursively which retrieves the child-elements for a specific parent. In situations where the menu has many items and/or has many levels this could easily result in dozens of queries being executed only to generate something simple as a treelike-output.

I would like to show you how this can be done using only a single query.

Let's take an easy example involving a database table called `menu` which has the following fields and contents:

idparentIdname
10Nieuws
20Reviews
30Meuk
41Games
51Internet
65Browsers

Here you'll see that all the 'root'-items have a parentId of 0 and child-items have the parentId set to the id of the item to which they belong.

Suppose we want to output a nested unordered list of these items sorted by name. In any kind of solution it is wise to have an index on `parentId` but in this case you might want to have an index on `parentId` and `name`. We start with our single query that retrieves all of the items:

PHP:

1
2
3
4
5
6
7
8
9
<?php
// get all menuitems with 1 query
$result = mysql_query("
    SELECT
        id, parentId, name
    FROM
        menu
    ORDER BY
        parentId, name
"
);
?>

Now we need to fetch all the items, and while we do that we also create a special array that defines which items are parents and what their direct children are:

PHP:

1
2
3
4
5
6
7
8
9
10
11
<?php
// prepare special array with parent-child relations
$menuData = array(
    'items' => array(),
    'parents' => array()
);

while ($menuItem = mysql_fetch_assoc($result))
{
    $menuData['items'][$menuItem['id']] = $menuItem;
    $menuData['parents'][$menuItem['parentId']][] = $menuItem['id'];
}
?>

You may want to do a print_r() on this array in order to fully understand what this is doing, but in any way it is not really rocket-science.

Now that we have this prepared array all we need is a function that creates the output for us (recursively in this case), and call this function:

PHP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<?php
// menu builder function, parentId 0 is the root
function buildMenu($parentId$menuData)
{
    $html = '';

    if (isset($menuData['parents'][$parentId]))
    {
        $html = '<ul>';
        foreach ($menuData['parents'][$parentIdas $itemId)
        {
            $html .= '<li>' . $menuData['items'][$itemId]['name'];

            // find childitems recursively
            $html .= buildMenu($itemId$menuData);

            $html .= '</li>';
        }
        $html .= '</ul>';
    }

    return $html;
}

// output the menu
echo buildMenu(0$menuData);
?>

You see: no more queries necessary, just a simple recursive function that creates the output. Happy programming!

Volgende: Oud & nieuw @ huize crisp 01-'08 Oud & nieuw @ huize crisp
Volgende: Banners en browsing performance impact 12-'07 Banners en browsing performance impact

Comments


By Tweakers user SchizoDuckie, Monday 24 December 2007 00:03

Is dit echt zo'n vorm van Rocket Science dat de gemiddelde programmeur hier niet op komt? :X Damn, ik moet ook m'n eigen weblog beginnen :+

By Tweakers user crisp, Monday 24 December 2007 00:18

Is dit echt zo'n vorm van Rocket Science dat de gemiddelde programmeur hier niet op komt?
Blijkbaar wel... ik schreef dit artikel met deze recente forumpost in mind, maar initieel werd hier op tweakblogs de categorie-structuur ook op een soortgelijke wijze (dus met meerdere sub-queries binnen een recursieve functie) samengesteld.

By Tweakers user NitroX infinity, Monday 24 December 2007 12:03

Is dit een single-level menu waarbij de namen van parents achter de <ul> tag worden geplaatst? (En de kinderen dus de <li>'s zijn?)

By Tweakers user crisp, Monday 24 December 2007 14:02

Hoe bedoel je de namen van parents achter de <ul>? Een <ul> mag alleen maar <li>'s bevatten, geen inline content. Dit genereert deze markup:

HTML:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
<ul>
    <li>Nieuws
        <ul>
            <li>Games</li>
            <li>Internet
                <ul>
                    <li>Browsers</li>
                </ul>
            </li>
        </ul>
    </li>
    <li>Reviews</li>
    <li>Meuk</li>
</ul>

By Tweakers user NitroX infinity, Monday 24 December 2007 14:27

Oh okee, nou begrijp ik het (de uitvoer dan, de code is nog een raadsel :P).

By Tweakers user MikeN, Tuesday 25 December 2007 01:43

Als je bijvoorbeeld een subset van de data wil ophalen en een heel groot menu hebt, of een andere hiërarchische ordening van data hebt kan het soms ook zinnig zijn je database wat werk te laten doen. Zie daarvoor uitleg over nested sets op http://dev.mysql.com/tech...es/hierarchical-data.html :)

By Tweakers user crisp, Thursday 27 December 2007 00:21

Interessant MikeN maar behoorlijk omslachtig alsnog, zeker bij het bijwerken van items. Je moet wel behoorlijk wat geneste data hebben wil je daar (performance) voordeel uit halen; bij relatief kleine trees is het denk ik nog steeds lonender om gewoon de hele tree 'in te laden' en daar vervolgens een subset uit te halen.

Verder is natuurlijk hier de hele insteek juist om de database te ontlasten; processing environments zijn bijzonder geschikt om load te kunnen verdelen aangezien je er daarvan eenvoudig meer van kan inzetten. Databases clusteren is vaak een dure en ingewikkelde grap...

By Tweakers user mithras, Thursday 27 December 2007 22:42

Toch denk ik dat je makkelijker af bent met een MPTT oplossing (of zoals MikeN zegt, nested tags). Hoewel het snelheidsverschil minimaal is, zal je met een MPTT oplossing je database minder belasten.
Het opvragen van de data gaat veel gemakkelijker, omdat je kan zeggen "haal alle items op tussen links = x en rechts = y". Bij een adjacent model moet je *dan* wel meer moeite gaan doen. Uiteraard kan je de hele tabel ophalen en die dmv processing environments alles vanaf een bepaald punt neerzetten, bij een MPTT lukt dit ala miliseconden ;)

De enige echte overweging die je imho moet maken is het "SELECT vs INSERT"; je kan bij een adjacent model zonder veel rompslomp een node *ergens* toevoegen. Bij nested tags moet je een relatief zwaardere update draaien:
UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
INSERT INTO tree SET lft=6, rgt=7, title='New_node';

Ik kom echter vaak tegen dat de select 100'en tot 1000'en keren vaker wordt gebruikt dan de insert, dus daarmee met een MPTT performance technisch gezien makkelijker af bent :)

Ik ben nu bijvoorbeeld ook een RBAC implementatie aan het ontwerpen waarbij de rollen aan groepen worden gekoppeld, inclusief afhankelijkheden. Ik heb nu dus ook al door dat je met nested tags de verantwoordelijkheden en de rang van de rol veel gemakkelijker bepaald kan worden (zo kan je bijvoorbeeld aannemen dat een item altijd zijn parent "overruled"). Met een adjacent model zou zoiets een regelrechte hel worden ;)

Een artikel wat alles echt makkelijk behandelt (die MySQL pagina bevat imho teveel tabellen en queries): http://www.sitepoint.com/article/hierarchical-data-database

By Ruben, Wednesday 27 August 2008 18:18

Is er ook iets mogelijk met een navigatie, dus dat ik makkelijk:

Nieuws > Games > Internet

uit de database kan halen?

Is dit ook recursief?

By Tweakers user ari, Friday 19 September 2008 18:28

De db van mijn website heeft ook het systeem waar mithras naar linkte, dus met een rgt en een lft (wat blijkbaar MPTT heet).

Als je dus een navigatie wilt zoals "Nieuws > Games > Internet", is dat vrij simpel (als je de lft en rgt hebt):


SQL:
1
SELECT name FROM table WHERE lft <= $lft AND rgt >= $rgt ORDER BY lft ASC;


Wel even $lft en $rgt netjes wegwerken in je code. ;)

By Manuel Carrizosa, Wednesday 08 October 2008 06:12

I've added a third parameter to the function named $dept, using it you can control how deep the menu sould be... hope you find it useful :)

function buildMenu($parentId, $menuData, $dept)
{
$html = '';

if (isset($menuData['parents'][$parentId]))
{
$html = '<ul>';
foreach ($menuData['parents'][$parentId] as $itemId)
{
$html .= '<li>' . $menuData['items'][$itemId]['nom'];
if($dept>1){
$html .= buildMenu($itemId, $menuData, $dept-1);
}
$html .= '</li>';
}
$html .= '</ul>';
}
return $html;
}

// output the menu
echo buildMenu(0, $menuData, 2);

By Manuel Carrizosa, Wednesday 08 October 2008 06:17

DON'T FORGET to replace nom with name in the script above in the line:

$html .= '<li>' . $menuData['items'][$itemId]['nom'];

It should be:

$html .= '<li>' . $menuData['items'][$itemId]['name'];

It's just because in my table the NAME COLUMN is named NOM. Sorry about that :(

By Anil, Tuesday 25 November 2008 14:14

Thanks a lot.

By Bostko, Monday 12 January 2009 02:10

Thank you very much! I'm glad I found your blog :)

By Stefan, Monday 12 January 2009 23:07

EXCELLENT! Thank you very much for this code!

By Tweakers user DelTorro, Tuesday 03 February 2009 20:59

Is het ook mogelijk om een multidimensionale array van deze tree te maken? Daar kom ik namelijk niet helemaal uit

By Annonymous, Thursday 12 February 2009 11:50

Hi,
Thanks for this excellent example.
How do we find depth of a menu item?
(for example if parentId = 0 then depth = 0, if first sub then depth = 1 etc)

Thank you very much.
TJ.

By David, Wednesday 18 February 2009 17:17

is it possible to set de menu in a dropdown box?

By NeXEA, Thursday 21 May 2009 02:22

Very nice. Can't wait to see how much of an improvement this is over my previous script.

By s, Saturday 13 June 2009 02:03

Sal


How I can get this source code with your function?


code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
<div id="navigation">

    <ul id="menu">
        <li><a href="index.html" title="Item">Item</a></li>
        <li>
            <a href="#" title="Item with a submenu" class="">Item with 1-layer submenu</a>
            <ul>

                <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                <li><a href="index.html" title="Submenu item">Submenu item</a></li>
            </ul>
        </li>
        <li>
            <a href="#" title="Item with a submenu">Item with 2-layer submenu</a>
            <ul>

                <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                <li>
                    <a href="#" title="Submenu item with submenu">1-layer submenu</a>
                    <ul>
                        <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                        <li><a href="index.html" title="Submenu item">Submenu item</a></li>

                        <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                    </ul>
                </li>
                <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                <li>
                    <a href="#" title="Submenu item with submenu">1-layer submenu</a>
                    <ul>

                        <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                        <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                    </ul>
                </li>

            </ul>
        </li>
        <li>

            <a href="#" title="Item with a submenu">Item with 3-layer submenu</a>
            <ul>
                <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                <li>
                    <a href="#" title="Submenu item with submenu">2-layer submenu</a>
                    <ul>
                        <li><a href="index.html" title="Submenu item">Submenu item</a></li>

                        <li>
                            <a href="#" title="Submenu item with submenu">1-layer submenu</a>
                            <ul>
                                <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                                <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                                <li>
                                <a href="index.html" title="Submenu item">Submenu item</a>

                                    
                                    <ul>
                                    <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                                    <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                                    </ul>
                                    
                                </li>
                            </ul>

                        </li>
                    </ul>
                </li>
                <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                <li>
                    <a href="#" title="Submenu item with submenu">1-layer submenu</a>
                    <ul>
                        <li><a href="index.html" title="Submenu item">Submenu item</a></li>

                        <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                    </ul>
                </li>

            </ul>
        </li>
        <li><a href="index.html" title="Item">Item</a></li>
        <li>

            <a href="#" title="Item with a submenu">Item with 1-layer submenu</a>
            <ul>
                <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                <li><a href="index.html" title="Submenu item">Submenu item</a></li>
                <li><a href="index.html" title="Submenu item">Submenu item</a></li>

            </ul>
        </li>
        <li><a href="index.html" title="Item">Item</a></li>
    </ul>


</div>


Tank you

By Tweakers user cariolive23, Sunday 09 August 2009 13:49

De waarde 0 voor de parentId's is niet correct, er is geen enkel id met deze waarde aanwezig. Een foreign key constraint zal dan ook mislukken.

Gebruik NULL wanneer er geen bekende waarde aanwezig is, wanneer er geen parent aanwezig is. Een FK kun je ook zo instellen dat een NULL wordt goedgekeurd. Met het gebruik van FK's kun je er ook voor zorgen dat een parent niet kan worden verwijderd zolang er childs aanwezig zijn, dat kan weer de nodige ellende voorkomen.

By Pietjepuk, Monday 05 October 2009 11:43

Super mooi artikel maar is het ook mogelijk als je op een van deze items klikt een tekstpagina uit de db te laden.

Dus je hebt een index.php met deze info.
En als je bijv op Nieuws klikt krijg je een pagina die opent in een centerdiv.
Als je op Games klikt verniewt de centerdiv met informatie uit de db over games.

Dus je hebt 1 pagina index.php en de rest wordt uit de database gehaald.

Ik hoop echt dat iemand hier wat informatie over kan geven want ik zoek al een tijdje naar een tutorital/script/handleiding enz om zo'n systeem te maken.

Comments are closed