Implémentation d'une structure de données hiérarchique dans une base de données

Il y a plus d'options que les deux que vous citez. Il y a:

• Liste d'adjacence (le "parent_id" on a presque tout le monde utilise)
• Imbriquée Jeux De
• Chemin Énumération
• Fermeture de la Table (aka Relation d'Adjacence)

Voir ma réponse à "Quel est le plus efficace/moyen élégant pour analyser une table à plat dans un arbre?"

Ou un couple de livres:

• "Des arbres et des Hiérarchies dans SQL pour les Smarties" par Joe Celko.
• "SQL Design Patterns" par Vadim Tropashko.

L'approche naïve pour l'analyse d'une liste d'adjacence nécessite beaucoup de requêtes, et pour les grandes listes peuvent prendre beaucoup de temps à construire dans la mémoire. Pour référence, l'approche naïve je fais allusion pourrait être résumés comme suit: Sélectionner tous les éléments, sans parents, Puis pour chaque élément de manière récursive obtenir ses enfants. Cette approche nécessite n+1 requêtes de base de données.

J'ai utilisé la méthode suivante pour construire une liste d'adjacence avec 1 de la requête. Sélectionnez tous les éléments de formulaire de la base de données. Le transfert de tous les éléments dans un tableau indexé par leur clé. Parcourir le tableau et lui affecter une référence de l'objet parent pour chacun de ses enfants. Parcourir le tableau à une seconde de temps et de supprimer tous les objets enfants, laissant seulement le niveau de la racine des objets.

Puisque vous avez mentionné pile LAMP, PHP code pour ce faire est à peu près comme suit:

<?php
// Assumes $src is the array if items from the database.
$tmp = array();

// Traverse the array and index it by id, ensuing each item has an empty array of children.
foreach ($src as $item) {
  $item['children'] = array();
  $tmp[$item['id']] = $item;
}

// Now traverse the array a second time and link children to their parents.
foreach ($tmp as $id => $item) {
  if ($item['parent_id'] != 0 || $item['parent_id'] !== NULL) {
    $tmp[$item['parent_id']]['children'][$id] = &$tmp[$id];
  }
}

// Finally create an array with just root level items.
$tree = array();
foreach ($tmp as $id => $item) {
  if ($item['parent_id'] == 0 || $item['parent_id'] === NULL) {
    $tree[$id] = $item;
  }
}

// $tree now contains our adjacency list in tree form.
?>

Veuillez noter que ce code est destiné à illustrer une technique pour la construction d'une liste d'adjacence à partir d'une seule requête de base de données. Il pourrait probablement être optimisé pour moins de consommation de mémoire, etc. Il n'a également pas été testé.

Jim,

L'autre approche est appelée "ensemble imbriqué", je pense, pas de "nested arbre".

De toute façon, une bonne chose à propos d'un plan du site est que vous savez peut-être sa profondeur maximale. Je pense que le problème de la proximité du modèle est que les requêtes SQL correspondant fonctionne sur un seul niveau à la fois, donc si vous avez des " n " niveaux, alors vous avez besoin d'une boucle de 'n' SQL ... mais je pense (je ne suis pas sûr) que si vous connaissez le maximum de " n " à l'avance, alors vous pouvez code correspondant fixe-nombre-de-plusieurs-niveaux SQL.

0,3 secondes sonne pour moi comme un très long temps à la figure de 200 pages, donc c'est probablement OK.

Également une carte du site n'est pas mis à jour très souvent; ainsi, même si elle prend du temps à récupérer à partir de SQL, vous pouvez probablement le cache de l'extrait/calculé arbre dans la mémoire RAM.

Alternativement, au lieu de se soucier de la SQL pour créer une arborescence, vous pouvez simplement le magasin le plus simplement possible (liste d'adjacence), le récupérer à partir de la base de données comme un simple ensemble de lignes, et construire l'arbre dans la mémoire vive (en utilisant des boucles dans votre langage de programmation) au lieu d'utiliser des boucles dans le SQL pour créer l'arborescence à l'aide d'instructions SQL.