Reprise du message précédent :
et pour le problème d'arborescence, que pensez-vous de ça : http://sqlpro.developpez.com/cours/arborescence/ (2. Représentation intervallaire des arborescense).  
Cette méthode me semble bien performante pour une arborescence avec de nombreux niveaux ou de nombreuses feuilles.  
 
Vous en pensez quoi ?

C'est interessant, je vais étudier ça de plus près.
 
Merci

disons que ça a l'air très séduisant ce principe, le truc qui m'ennuie c'est que une suppression ou une insertion va demander la modification de pas mal de lignes dans la table.
 
Les pros de l'optimisation en pensent quoi ? ( http://sqlpro.developpez.com/cours/arborescence/ (2. Représentation intervallaire des arborescense).  )

Euh, au-secours les suppressions et insertions de sous-arbres...
 
(même si c'est moins lourd que la solution avec des chaines de caractères...)

bah en meme temps est-ce que c'est pire qu'une fonction récursive permettant de récupérer tous les enfants ou parents d'un élément dans une représentation classique (point 1 du lien)

Ca se discute.
Il faut voir le contexte : La table est grosse? On peut se permettre de locker une grosse partie de la table pour une bête insertion? On fait bcp de suppressions/insertions, ou bien c'est marginal? La charge du programme est plutôt sur le serveur SQL ou sur le serveur d'appli?

personnellement, je dois représenter un arbre avec plusieurs dizaines de niveau, plusieurs milliers d'éléments, sur lequel on doit faire souvent des selects, beaucoup plus que des insertions et des suppressions. Ca semble donc pas mal cette méthode dans ce cas non ?

dans ce cas oui, ça me parait raisonnable.

idée d'organisation à voir, mais petite question : pourquoi considéret'il qu'il faut que chaque élément prenne deux places? N'est il pas possible de simplement noté comme fin d'intervale le plus grand id du contenu de l'intervale?
On se retrouverait alors avec le même nombre de numéros attribués que d'éléments au lieu d'en utiliser le double.
 
Dire que pour une des tables de mon site je m'étais emmerdé à mettre au point un systéme complexe pour accéler les sélections dans cette table alors que cette méthode là l'est au moins autant en étant plus simple.  

Ah non, il ne prend pas 2 "places"...il compte le nombre d'éléments rencontrés jusque là dans son parcours de l'arbre. Ce nombre est différent à "l'aller" et au "retour"...et sans ça je ne vois pas comment ça pourrait marcher!

je pense que c'est surtout pour simplifier les requetes select : on a pas besoin de connaitre la borne droite de l'élément précédent.

euh nan, si on se contente de les numéroter on ne sait même pas reconstituer l'arbre, quoi! Comment tu déterminerais si 6 est le fils de 5 ou plutôt son frère?

Ben moi, je vérais plustôt une non incrémentation quand on remonte qu'une incrémentation à l'allé et au retour.
 
En gros, un éléments qui a trois descendant aurait l'indicateur de fin d'intervale égal à son indice personel plus 3.
De maniére plus générique, on se retrouverait avec indice de fin d'intervale = indice de début d'intervale + nombre d'enfant.
Avec sa méthode à lui, on a indice de fin d'intervale = (indice de début d'intervale *2) +1. Moins facile donc pour savoir le nombre de descendant.

>omega2 : je vois pas trop la diff : soit tu stock un indice, et le nombre d'enfants, soit tu stocke borne gauche et droite
ou alors j'ai rien compris à ce que tu dis ^

Je suis pas super fan d'avoir plusieurs éléments avec le même nombre à droite...t'as une différence stricte d'un coté et pas de l'autre, c'est le meilleur moyen de faire une erreur à la con...

et ça va compliquer la recherche du complément d'un sous-arbre, tiens.

Avec mon idée, pour retrouver le pére d'un élément, il suffit de chercher celui dont l'id propre est le plus grand tout en étant < à l'id de l'élément de référence et dont l'id de fin d'intervale est plus grand que l'id de l'élément de référence. C'est certe un peu plus long mais c'est négligeable avec un bon index même sur de grosses tables.
 
Pour rechercher l'ensemble des ancêtres d'un élément, on cherche ceux dont l'id de fin est >= à l'id de fin de l'élément et dont l'id propre est < à l'id de l'élément de référence. Là, c'est identique avec la méthode d'origine.
 
Et si tu veux savoir si l'élément précédant n'est pas un ancêtre, il suffit que tu regardes si l'id de fin d'intervale est inférieur à l'id de l'élément en cours.
 
 
Finalement sur de grosses tables, pour savoir quelle est la méthode la plus rapide, il faudrait savoir si la base va perdre plus de temps à faire de temps en temps des select un peu plus complexe ou si elle en perdra d'avantage en manipulant des éléments de taille double (passer un certain nombre d'éléments, il faudra passer aux longint alors qu'avec ma méthode, on sera encore en simple integer) à chaque select/update/insert/delete .

...et probablement certaines insertions, aussi.

 
Ouais enfin avant d'avoir besoin de plus qu'un integer il va te falloir un sacré arbre hein...et là je préfère même pas envisager cette solution, laisse tomber le cout des modifications de l'arbre...

Si tu codes comme un goret, peut être, si tu codes proprement en respectant l'architecture choisit, il n'y a aucune raison vu que t'as bien un id unique pour chaque élément. Je ne voit vraiment pas en quoi ca serait dangeureux a moins de ne pas faire gaffe à ce qu'on fait.
 

Pourquoi ça? Les descendants, c'est ceux dont l'id propre est supérieur à l'id de l'élément de référence et donc l'id de fin d'arborescence est inférieur ou égal à celui de l'élément de référence.
Avec la méthode d'origine, c'est pareil à par que t'as un inférieur strict au lieu d'un inférieur ou égal.

dsl, mais je comprends pas pourquoi ta méthode diminuerait de moitié les données stockées :  
dans ton cas on stocke l'indice et le nombre d'enfants non ? et dans leur cas on stocke une borne gauche et une borne droite. C'est ou que je loupe un truc ?

 
Non.
Le complément d'un sous arbre avec la méthode d'origine c'est les éléments qui vérifient :
gauche < gauche de la racine  
ou
droite > droite de la racine.
 
Vazy, fais aussi simple avec ta méthode.

Je vois pas en quoi les insertions serait plus ou moins couteuse dans un cas ou dans l'autre.

Super donc pour toi le sous arbre est l'arbre complet. Ce n'est pas un ou mais un "et" vu qu'il faut que ca soit entre les deux bornes avec la méthode d'origine.
Et aussi simple avec ma méthode.
gauche <= gauche de la racine
et  
droite > droite de la racine
 
 
PS : Je crois qu'on peut arrêter là la discution, ceux qui la liront se feront leur propre opinion et j'ai l'impression que ni toi ni moi ne changera d'avis donc autant en rester là.

Regarde le point 2.11, et réfléchis à ta solution...

 

Tu sais ce que c'est le complément d'un sous-arbre oui ou non?
http://sqlpro.developpez.com/cours/arborescence/#L2.6

je me permets de up ma question

Djebel1 > On stocke l'indice de début et l'indice de fin mais comme chaque élément ne provoque une incrémentation et pas deux alors on peut en gérer deux fois plus pour une taille de colone donnée.

c'est tout con : tes chiffres augmentent 2 fois plus vite, donc tu vas atteindre 2 fois plus vite le chiffre le plus grand permis par le type integer...donc pour stocker autant d'élément il te faut plus de place.
 
M'enfin comme dit plus haut il faudrait atteindre un nb d'éléments énorme pour que ce soit gênant, auquel cas gérer un arbre de cette manière ne me paraitrait pas une bonne idée..;

ha oui oki, merci

Bon ben je n'arrive pas mieux m'en sortir avec cette méthode
 
Imaginons l'arborescence suivante :
 

 
Je fais comment si je veux déplacer mon "DOSSIER A" pour le placer *sous* "DOSSIER B", et donc avoir ça :
 

Pitetre en commençant par supprimer le sous-arbre DOSSIER A (point 2.13) et en le stockant dans une table temporaire, puis en le réinsérant sous DOSSIER B.
 
J'avoue, c'est pas économique, mais je vois pas trop comment faire sinon. Ils disent bien que ce truc est efficace surtout pour les select ^^

Ya tout ce qu'il faut dans l'article, non?

non ils parlent pas vraiment de déplacement, juste d'insertions et de délétions, et disent bien que c'est surtout efficace pour les select.
 
mais en deux étapes avec une table temporaire, ça doit le faire

Bon ça me gave, c'est beaucoup trop complexe pour gérer les déplacement, même avec une table temporaire.
 
Pourtant c'est pas la mer à boire ce que je veux faire. C'est dingue que MySQL ne permette pas de faire un truc aussi "bête"
 
Sinon il n'y a pas moyen de bidouiller avec les clé étrangères. Genre pouvoir supprimer virtuellement histoire de voir tous les ID affectés par la suppression d'un parent ... enfin je sais pas moi, ça m'enerve.
 
Je veux faire un truc tout con et il n'y a aucun moyen simple d'y parvenir. C'est quand même assez commun non de gérer des liens de parentée

perso j'ai passer quelques temps sur la question pour un stage, en stockant simplement dans la base l'id d'un élément avec l'id de son parent. Bah non, y avait pas de moyen simple de le faire  
j'ai du y aller à gros coups de fonctions récursives. Et le système décrit ici m'a eu l'air plus intéressant, je vais tenter de migrer la base avec ce système je pense
 
Donc je serais toi, je crois que j'insisterai avec ce système. M'enfin c'est toujours pareil, si tes requetes c'est surtout des insert update et  delete, vaut mieux passer par un système classique en stockant l'id du parent je pense

Normallement ça devrait être surtout du SELECT et de l'INSERT, quelques DELETE, de rares UPDATES
 
Je verrais, je fais une pause dans le developpement là, le temps de m'aérer un peu
 
En tout cas merci pour votre aide !

sinon au niveau de l'affichage, ca donnerai quoi?

Une arbo de liens classés dans différents dossiers.
 
Mais j'ai laissé tomber le développement pour le moment, je suis sûr un autre projet (ràv avec la prog)

la gestion via tableau php est encore la plus simple et c'est pas si gourmand que ce qu'on pourrait croire

Perso, pour un outil de revue en ligne, je devais permettre la création d'un sommaire (une arbo en somme). La table était la suivante :  
ID, Libellé, N° d'ordre, ParentID
 
Le n°ordre permettait la création des rubriques du sommaire dans un ordre différent de celui de l'affichage. Sinon, pour la génération de l'arbo, ben comme proposé, un tableau php qui contient la table entière puis un autre tableau qui contient l'arbo et qui se construit de manière récursive en parcourant le premier tableau