Comment récupérer le chemin d'un nœud dans un arbre - efficace (lié au poste 'analyser une table plate dans un arbre?)

Question

Cette question fait suite à ce poste:

What is the most efficient/elegant way to parse a flat table into a tree?

J'ai aimé la solution ClosureMap, mais j'ai un problème supplémentaire à résoudre.

Comment pouvez-vous facilement récupérer le chemin d'accès à un nœud particulier dans un arbre? Par exemple, si vous regardez l'arbre fourni:

ID Nom du noeud

1 'nœud 1'
2 'Node 1.1'
3 'Node 2'
4 « Node 1.1. 1'
5 'Noeud 2,1'
6 'Noeud 1,2'

Le chemin vers 1.1.1 serait:

ID = 1, 2, 4

Sans effectuer d'appels SQL récursifs, existe-t-il un moyen élégant de récupérer un chemin?

Answer 1

SELECT ancestor_id 
FROM ClosureTable 
WHERE descendant_id = 4; 

Renvoie les valeurs 1, 2, 4. Mais ils sont retournés sur des lignes séparées, et ils ne donnent aucune indication qu'ils sont dans l'ordre (on peut pas supposer l'ordre numérique correspond à l'ordre de la hiérarchie des arbres) .

Parfois, vous pouvez également stocker la profondeur de chaque chemin dans le ClosureTable. Mais même si pas, vous pouvez compter le nombre d'ancêtres un noeud donné a, et l'utiliser pour trier:

SELECT ct1.ancestor_id, COUNT(*) AS depth 
FROM ClosureTable ct1 
JOIN ClosureTable ct2 ON (ct1.ancestor_id = ct2.descendant_id) 
WHERE ct1.descendant_id = 4 
GROUP BY ct1.ancestor_id 
ORDER BY depth; 

Oui, cela renvoie toujours le résultat en trois lignes. Si vous utilisez MySQL, vous avez accès à GROUP_CONCAT(). Sinon, il est facile d'aller chercher trois lignes et de concaténer leurs valeurs dans le code de l'application.

Answer 2

Je pense avoir trouvé la meilleure solution, et je ne me suis pas vraiment rendu compte que c'est dans le post auquel j'ai fait référence :).

point du site a eu un bel article qui montre la façon de récupérer un noeud spécifique en utilisant la gauche/droite Attributs:

http://www.sitepoint.com/article/hierarchical-data-database/2/