![[RSS]](http://tweakimg.net/g/if/v2/icons/rss_small.png){kind=icon}
![[quick]](http://tweakimg.net/g/if/icons/world_link.png){kind=icon}
Formatting a multi-level menu using only one query
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:
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:
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:
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:
You see: no more queries necessary, just a simple recursive function that creates the output. Happy programming!
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:
| id | parentId | name |
| 1 | 0 | Nieuws |
| 2 | 0 | Reviews |
| 3 | 0 | Meuk |
| 4 | 1 | Games |
| 5 | 1 | Internet |
| 6 | 5 | Browsers |
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:
| <?php
|
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:
| <?php
|
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:
| <?php
|
You see: no more queries necessary, just a simple recursive function that creates the output. Happy programming!
01-'08 Oud & nieuw @ huize crisp
12-'07 Banners en browsing performance impact
Comments
By
SchizoDuckie,
Monday 24 December 2007 00:03
Is dit echt zo'n vorm van Rocket Science dat de gemiddelde programmeur hier niet op komt? 
Damn, ik moet ook m'n eigen weblog beginnen 
Damn, ik moet ook m'n eigen weblog beginnen
By
crisp,
Monday 24 December 2007 00:18
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.Is dit echt zo'n vorm van Rocket Science dat de gemiddelde programmeur hier niet op komt?
By
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
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:
HTML:
1 | <ul>
|
By
NitroX infinity,
Monday 24 December 2007 14:27
Oh okee, nou begrijp ik het (de uitvoer dan, de code is nog een raadsel 
).
).
By
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
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...
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
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
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
Is er ook iets mogelijk met een navigatie, dus dat ik makkelijk:
Nieuws > Games > Internet
uit de database kan halen?
Is dit ook recursief?
Nieuws > Games > Internet
uit de database kan halen?
Is dit ook recursief?
By
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:
Wel even $lft en $rgt netjes wegwerken in je code.
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.
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);
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);
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
$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
Thanks a lot.
Thank you very much! I'm glad I found your blog
EXCELLENT! Thank you very much for this code!
By
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
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.
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.
is it possible to set de menu in a dropdown box?
Very nice. Can't wait to see how much of an improvement this is over my previous script.
Sal
How I can get this source code with your function?
code:
Tank you
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
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.
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.
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.
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
