Stocker des données hiérarchisées dans une base de données - Partie 1

Il est fréquent d'avoir à stocker des données hiérarchisées comme une liste de catégories dans une base de données. Malheureusement, les bases de données relationnelles comme MySQL ne proposent pas de fonctions spécifiques pour ce type de structure.

Je vous propose d'examiner, à travers un exemple, les différentes solutions qui sont disponibles.

Imaginons un magasin informatique en ligne qui aurait les catégories suivantes :

Le premier type de structure qui vient à l'esprit est le suivant :

id	parent_id	name
1	0	Périphériques
2	1	Claviers
3	1	Souris
4	1	Imprimantes
5	4	Jet d'encre
6	4	Laser

Pour imprimer l'arborescence, on peut utiliser la fonction récursive suivante :

function display_children($parent_id, $level = 0) {
// Retrouve tous les enfants du parent $parent_id
$result = mysql_query('SELECT id, name FROM categories WHERE parent_id = '.$parent_id);

// Affiche chaque enfant
while ($row = mysql_fetch_array($result)) {
// Indente et affiche le nom de chaque enfant
echo str_repeat('  ', $level) . $row['name'] . "\n";

// Appelle la fonction pour chaque enfant
display_children($row['id'], $level + 1);
}
}

Pour afficher l'arbre entier, il suffit de faire :

display_children(0);

Pour imprimer uniquement les enfants du noeud "Imprimantes" :

display_children(4);

Ca a l'avantage d'être simple, mais ce n'est pas très performant, car on lance une requête SQL pour chaque noeud. Vous noterez au passage qu'il est conseillé de placer un index sur la colonne parent_id. Dans notre exemple, les catégories ne sont pas très nombreuses et changent rarement. On peut donc utiliser des techniques de cache pour éviter de trop solliciter la base de données. Pour afficher le chemin d'une catégorie dans la fiche d'un article, on peut utiliser la fonction suivante :

function get_path($node_id) {
// Recherche le noeud
$result = mysql_query('SELECT id, name, parent_id FROM categories WHERE id = ' . $node_id);
$row = mysql_fetch_array($result);
$path = array($row['id'] => $row['name']);

// On boucle jusqu'à ce qu'on arrive sur un noeud sans parent
while ($row['parent_id'] != 0) {
$result = mysql_query('SELECT id, name, parent_id FROM categories WHERE id = ' . $row['parent_id']);
$row = mysql_fetch_array($result);
$path = array($row['id'] => $row['name']) + $path;
}
return $path;
}

Par exemple, pour afficher le chemin de la catégorie "Jet d'encre" :

echo implode(' > ', get_path(5)); // Affiche Périphériques > Imprimantes > Jet d'encre

Dans un prochain article, je vous montrerai comment charger un Ext.tree.TreePanel. A voir également

• http://www.sitepoint.com/article/hierarchical-data-database
• http://dev.mysql.com/tech-resources/articles/hierarchical-data.html