bonjour,
 
j'essaye de faire un menu déroulant issu d'une requete sur une bd pour afficher l'arborescence du site.
 
dans la base chaque rubrique à un ID "secteur" "id_rubrique" et"id_parent"  
une rub à la racine a donc id secteur =0 id parent =0 et id rubrique=1(par ex)
une sous rub de celle ci aura id secteur =0 id_parent=1 et id_rubrique=2 (vous aviez compris !)
 
et je voudrais afficher dans le menu déroulant que l'arborescence soit respectée avec un décallage horizontal pour le titre des rub selon le niveau ou elles se situent ... je pense en plus que cela doit-êtr epossible de faire une seule requete en boucle pour que selon qu'elle trouve des descendant elle continue..  
j'ai fait un truc qui marche mais qui n'est surement optimisé et qui ne permet pas d'avoir l'ordre .. j'essaye selon l'ORDER BY .. mais j'y arrive pas  
 çà donne :  
<option value="0,,racine" selected>rubriques :</option>
 <?php  $res = mysql_query("SELECT id_rub,id_secteur,id_parent,rub_titre FROM $tbl_rubs ORDER BY id_parent ASC" ) ;
 
  while( $ligne = mysql_fetch_object($res) )
   {
  echo "<option value=\"$ligne->id_secteur,$ligne->id_rub,$ligne->id_parent\">- ".stripslashes($ligne->rub_titre)."" ;
 
}
echo "</select> ";
?>
 
une idée pour m'aider ?
merci
antoine
 
 

l'histoire des secteurs j'ai pas trop compris mais disons qu'il est fixe pour l'exemple
 
un resultat possible serait
secteur  rubrique  parent
   0           1           0
   0           9           0
   0           2           1
   0           3           1
   0           4           1
   0           5           2
   0           6           2
   0           7           3
 
tu veux un affichage du genre
rub1
   rub2
     rub5
     rub6
   rub3
     rub7
   rub4  
rub9
 
donc en une requete c pa possible
faut faire un parcours en profondeur recursif (ou iteratif avec un pile mais plus chiant a faire)
 
pour facilité l'algo l'ideal c de faire une liste d'adjacence avec les sous rubriques pour chaque rubrique
 
genre  
1 : 2 ~ 3 ~ 4
2 : 5 ~ 6
3 : 7
4 : ø
5 : ø
6 : ø
7 : ø
8 : ø
9 : ø
 
l'algo en gros
 
ajouter_recursif(rubrique,profondeur)
 {
 ajouter dans la liste deroulante rubrique (identer en fct de profondeur)
 tant que rubrique a des sous rubrique
   ajouter_recursif(sousrubrique,prodondeur+1)
   supprimer la sousrubrique traité dans la liste d'adjacence de rubrique
 }
 
t'appelle ajouter_recursif(rubrique,0) pour toute les rubrique de parents 0
et ca devrait etre bon

merci de ta réponse .. j'avoue que çà me parait pas évident ..
le fonction ajouter_recursif(rubrique)  serait une autre requete ?
> une variable pour sauvegarder la profondeur  
comment tu fais çà ?
si tu peux m'éclairer ..

j'ai actualisé qd tu repondais... dsl
il faut d'abord cree la liste d'adjacence
avec la reponse du ton mysql_query
 
ensuite appeller la fonction php ajouter_recursif(rub,0)
 
pour la liste d'adjacence en fait c un tableau php
dont les indices sont les rubriques et la valeur par exemple une enumeration separé par des virgules des sous rub
 
par exemple
 
$tab[1]="2,3,4;"
$tab[2]="5,6";
apres tu explode $tab[i] par exemple pour avoir un tableau des sous rub de rub i
 
pour profondeur l'algo que je t'ai donné s'en oqp qd on appelle recursivement ajouter_recursif la profondeur est augmenté de 1
qd je dis ajouter la rubrique dans la liste deroulante, tu peux te servir immediatement de la variable  profondeur qui correspond au nombre d'indentation à faire

si tu fais pas d'etudes d'infos c va pas etre evident en effet deja que moi ca me soulerait de le faire, lol
relis tout car g fait des corrections

j'ai un système similaire, qui prend une liste (obtenue d'un stockage à la SQL) pour la convertir en une structure multidimensionnelle (à la xml : nodes et children) ...  
ouais, au départ, j'étais parti sur un truc récursif (rubrique, parent) que j'ai finalement laché pour qlque chose de linéaire bcp plus simple et énormément plus facile à maintenir (ordre, profondeur) avec des requêtes SQL ...
 
conclusion : avec la méthode 2 (en linéaire) je ne fais qu'une seule itération de ma liste originale, alors qu'avec la méthode récursive tu dois soit maintenir un index d'ordre en plus de "rubrique" et "parent" soit faire une pré-itération pour générer ce que Vlad' appelle la liste d'adjacence ...  
 
mais bon, j'te raconte pas les paquets de café utilisé dans cet algo ...  

le parcours en profondeur (recursif ou iteratif avec une pile) est optimale pour ce type d'operation
niveau sql cout minimum (juste recupérer les données sans les trier meme pas besoin de order)
la liste d'adjacence est en 0(n) autant d'operation que de ligne
y'a y a juste la prog qui demande un petit effort
 
que tu stockes dans une liste d'adjacence, une matrice ou une structure multidimensionnelle, il faudra bien faire une iteration pour respecter l'arborescence et c la toute la difference.
 
j'ai reflechi un peu et la seul autre methode pour s'en sortir serait de recuperer les données triés par parent et de calculer la position de chaque rubrique et sa profondeur pour les n lignes et reiterer celle déja ajouter pour les mettre a jour
 
genre: (par rapport à mon exemple post ci-dessus)
 
rub 1 : position 1 profondeur 0
rub 9 : position 2 profondeur 0
rub2 : position 2 (car c un fils de rub1 donc il doit etre en dessous) profondeur 2 (profondeur du pere + 1)
donc je dois mettre a jour s'il y en a les rub de profondeur 0 autre que le parent de rub2 (rub1) donc rub 9
rub 9 : position 3 profondeur 0
rub3 : position 3 (fils de rub1) profondeur 1
donc je met a jour rub 9
rub9 : position 4 profondeur 0
etc
 
d'une c n'est pas du tout linéaire (c n'est pas parce que c'est iteratif que c linéaire)
linéaire ca serait genre n lignes a traiter n itérations (ou appel recursif) mais je crois qu'on utilise rarement ce terme
la c du 1+2+3+4+...+n=n(n+1)/2 soit en O(n²) la ou le parcours en profondeur fait du O(n)
 
bref c tres tres couteux!
mais plus facile a mettre en oeuvre pour un autodidacte (l'algo de parcours en profondeur on ne le pond pas tout seul meme si qd on y regarde de plus pres ca parait logique )

ok autant pour moi le terme 'linéaire' 'est inaproprié. Je l'ai utilisé pour différencier l'itération simple de la récursivité. Je voulais mettre l'accent sur la différence entre
1. méthode recursive : une boucle récursive + stockage de la rub. + stockage de l'id du parent + une itération ou un stockage supp. pour la liste d'adjacence + stockage d'un index
2. méthode itérative simple : une itération + stockage d'un index + stockage de la profondeur
 
Et comment gères-tu l'ordre d'arrivée des parents, de deux enfants d'un même parent, comment savoir qui est avant qui ?
Notes donc que la solution récursive n'est pas correctement maintenable sans un index d'ordre ...
tu es obligé de maintenir un index d'ordre dans la méthode récursive.
la maintenance SQL, comment fais-tu pour déplacer une branche entière sous une autre branche, ou à la racine ?
1. méthode récursive : tu dois mettre à jour la rub + les parents + ton index d'ordre
2. méthode itérative simple : mise à jour de l'index d'ordre + profondeur
- donc toi, tu ne trouves pas "tres tres couteux" de gérer parent-rub-ordre, de réitérer ou de stocker une liste d'adjacence, puis finalement de balancer le tout dans une boucle récursive ?
 

bah non ...
si tu as juste l'ordre et la profondeur, tu n'as pas besoin de plus ... pour faire _une seule_ itération.
 

  excuses moi, mais je te dirais bien de parler pour toi ...
  ce qui parait le plus logique n'est pas forcément le plus simple - mais ce qui est le plus simple parait le plus logique, non ?

Pour mon forum, j'ai opté pour une organisation qui permet d'aficher les discution par ordre chronologique ou pas arborescence.
 
pour faire ça, j'ai dans ma base :

• le numéro de réponse dans la dikscution (ordre chronologique)
• le numéro de la réponse auquel on a répondus
• la position d'affichage en mode arborescence sous forme d'un nombre (une réponse à un messge qui n'est pas le dernier entraine un décalége de tous les messges qui s'affichent en dessous de celui qauquel on répond)
• le niveau d'arborescence (entre autre pour le décalage)

Ca m'évite de faire des requettes de maniére récursive. Par contre, c'est vrai qu'au début, j'y ai passé du temps avant d'arriver à avoir toutes les données comme il faut.
 
 
Au boulot, l'ancien webmaster a opté pour une arborescence dont les positions de messages sont notés par des suites de lettres par exemple "bc" veut dire troisiéme réponse au second message de niveau 1. Ca permet d'avoir en une seule donnée le niveau d'imbrication et la position d'affichage ('il suffit de trié sur cette colone) et ca évite de devoir modifier cette information quand on insére un nouveau message, mais par contre, ca prend vite plus de place dans la base de donnéek, la base de donnée mettra plus de temps à trier les donénes, ca nécessite un petit traitement pour savoir à quel niveau d'imbrication correspond chaque message et ca limite le nombre de réponse possible à un message donnée. Donc des avantages et des inconvénients.
 
Comme tu vois, il y a plusieurs solutions possible pour éviter la récusrsivité, mais si rien n'a été prévus pour disposer directement de l'odre d'affichage, il faudra la calculer de maniére récursive.

Faux :

• avec la manéire récursive, il sffit de changer la colone "fils de" de la tête de la branche qu'on veut déplacer.
• En itératif simple, par contre, on se retrouve à devoir faire plusieurs traitements.

C'est quasiment le seul cas où l'organisation récursive est plus efficace que le stockage de l'ordre d'affichage.

et l'ordre alors ?
parce qu'avec les "children" tu organises comment ?

j'ajouterais :
moi aussi et pour le plaisir, je vais crier : "Faux" !    
parce que tu aurais une manière de faire tout ce qu'il a été exposé, avec juste un champs "fils de", whaou, je suis impressionné ...

je rappel que jhac veut afficher l'arborescence de son site dans une liste deroulante.
il n'a pas parler d'ordonnance pour les rubriques de meme niveaux
S'il le veut il suffit d'ajouter une colonne pour ordonner les rubriques d'un meme niveau comme ci-dessous)
 
un resultat (order by parent,ordre) possible serait donc
 
rubrique  parent  ordre | position
   9           0        1    |    1
   1           0        2    |    2
   4           1        1    |    3
   2           1        2    |    4
   3           1        3    |    7
   6           2        1    |    5
   5           2        2    |    6
   7           3        1    |    8
 
ce qui devrait donner
rub9
rub1
   rub4
   rub2
     rub6
     rub5
   rub3
     rub7
 
liste d'adjacence (n itérations)
0:  9 ~ 1
1 : 4 ~ 2 ~ 3
2 : 6 ~ 5
3 : 7
4 : ø
5 : ø
6 : ø
7 : ø
8 : ø
9 : ø  
 
bref rien de compliqué ni couteux
l'algo de parcours reste le meme vu qu'il ajoutera les rubriques en respectant l'ordre de la liste d'adjacence
 
on va tout de meme calculer c que ferai l'algo
que je rappel et modifie en consequence
 
arbo_recur(rub,p,l)
/*
  rub : n° de la rubrique
  p : profondeur de rub
  l : liste d'adjacence (tableau)
*/
debut
 si (rubrique != 0) alors
   ajouter dans la liste déroulante p indentations + rub
 tant que l[rub] non vide
   arbo_recur(tete de l[rub],p+1,l)
   supprimer la donné en tete de l[rub]
 fintantque
 }  
 
executons l'algo...
on appelle arbo_recur(0,0,l)
  rub=0, on ajoute rien dans la liste deroulante
  l[0] est non vide
  on appelle arbo_recur(9,1,l)  
    rub=9, on ajoute 9 dans la liste deroulante                                      9
    l[9] est vide, on sort
  on supprime 9 de l[0]  
  l[0] est non vide
  on appelle arbo_rescur(1,1,l)
    rub=1, on ajoute 1 dans la liste deroulante                                      1
    l[1] est non vide
    on appelle arbo_recur(4,2,l)
      rub=4, on ajoute 4 dans la liste deroulante                                      4
      l[4] est vide, on sort
    on supprime 4 de l[1]
    l[1] est non vide
    on appelle arbo_recur(2,2,l)
      rub=2, on ajoute 2                                                                      2
      l[2] est non vide
      on appelle arbo recur(6,3,l)
        rub=6, on ajoute                                                                          6
        l[6] est vide on sort
      on supprime 6 de l[2]
      l[2] est non vide
      on appelle arbo_recur(5,3,l)
        rub=5, on ajoute                                                                          5
        l[5] est vide on sort
      on supprime 5 de l[2]
      l[2] est vide on sort
    on supprime 2 de l[1]  
    l[1] est non vide
    on appelle arbo_recur(3,2,l)
      rub=3, on ajoute                                                                         3
      l[3] est non vide
        on appelle arborecur(7,3,l)
          rub=7, on ajoute                                                                        7  
          l[7] est vide, on sort
      on supprime 7 de l[3]
      l[3] est vide, on sort
    on supprime 3 de l[1]
    l[1] est vide, on sort
  on supprime 1 de l[0]
  l[0] est vide on sort
terminé
 
n+1 appelle donc O(n) optimal
 
Pour en revenir a vos reponses
shakpana

 
parent rub ordre c le minimum pour faire ce que l'ont veut
stocker dans une liste d'adjacence est optimale, n itérations et les données sont directement prete a être utiliser
questionner la base à coup de mysql_fetch_array est plus couteux dans ce contexte car l'algo utilisé derriere est en O(n²).
=> la structure de liste d'adjacence permet d'economiser ensuite sur le nombre d'iterations (meilleur algo utilisé par la suite)
fonction recursive : optimal, n+1 appelle
 

// pour l'algo sans parcours
qd tu affecte un ordre et une profondeur à une rubrique ils ne sont que provisoires.
exemple
tu veux
rub9
  rub2
rub1
 
le tableau mysql retourne
rub  ordre  profondeur  
9       1          0
1       2          0
2       1          1
 
rub1 va etre placé avant rub2
 
rub9
rub1
  rub2
 
il faut mettre a jour l'ordre des rubriques comprise entre rub2 et son pere
bref relis mon exemple parce que la t'es completement largué

Je trouve ça un peu présomptueux comme raisonnement ...
- acceuil, rub1, rub2, contact, crédits
risque de se retrouver
- acceuil, crédits, contact, rub2, rub1
si l'on ne créé pas tout le bon ordre et comment ferait-on si voulait mettre rub2 avant rub1 ?

donc tu te retrouve à gérer en plus un index d'ordre, merci.

ben si, car tu gères les relation parents/enfants PLUS l'ordre
Or il est possible de gérer seulement l'ordre et la pronfondeur ... sans ce soucier du nom du parent ou des enfants

je ne sais où tu as vu plusieurs mysql_fetch_array ?
il est possible de faire une lecture SQL + une itération simple et de se retrouver avec une structure multidimensionelle sans aucune liste d'adjacence ni aucune pre-itération.
Pour l'écriture Ajout ou Modif, il faut connaitre le point cible d'insertion|réaffection (son ordre) et son niveau, puis une requête SQL pour décaler l'ordre et une deuxième requête pour l'insertion/modification de la source
 
lecture : une requête SQL, une itération
écriture : lecture + une itération pour correction de la profondeur s'il y a lieu + une requête SQL UPDATE order = order (+|-) 1 + une requête SQL INSERT|UPDATE
 
mais bon ...

tu arrives a ordonner les rubriques de meme niveau sans en avoir l'information, tu es tres fort
 
le probleme c'est que tu ne differencies pas la phase de construction et la phase d'utilisation
pour la construction on a besoin de l'ordre et du parent de chaque rubrique (ou l'ordre est l'ordonnance des rubriques de meme niveau)
cette construction implique l'affectation de la position finale de chaque rubrique et leur profondeur
de cette facon la lecture est optimal : order by position et c'est fini
 
la liste d'adjacence est construite avec une unique itération de la table comme toi et ta structure multidimensionnelle
ensuite l'algo de parcours (construction) effectue le travail en n+1 appel recursifs, le tient est moins performant car il n'ajoute pas en respectant immediatement l'arborescence, il doit mettre a jour.  
 
Prenons le cas ou tu dois inserer une nouvelle rubrique entre une rubrique et une de ses sous rubriques ca serait vraiment terrible pour ton algo;
l'algo en profondeur le ferait toujours en n+1 appels au pire la ou le tient mettra sans cesse les positions a jour
 
En esperant avoir été clair, j'abandonne si tu ne toujours comprends pas

> il faut mettre a jour l'ordre des rubriques comprise entre rub2 et son pere
> bref relis mon exemple parce que la t'es completement largué
ouais, tu sais quoi, c'est moi qu'arrête là.
je te répête une truc 15 fois, et tu ne veux même pas l'envisager, tu restes campé sur tes positions, c'est un peu fatiguant, quant à celui qui ne comprend pas à priori c'est toi, mais une bonne relecture du thread t'éclaireras un peu. J'ai un système itératif/récursif qui fonctionnait à merveille, que j'ai remplacé par un système beaucoup plus simple et plus rapide seulement itératif.
donc en gros tout ce que tu me racontes j'y suis déjà passé, et je sais déjà que çà marche, ok ?
à bon entendeur ...
 
je te laisse ça puis après ...

quant tu l'auras sous cette forme en une seule itération, tu m'en reparles ...
edit : et que tu pourras le maintenir en 2 requête SQL avec un UPDATE order et un INSERT|UPDATE

J'ai pas lu tout le bazar en entier mais si jamais ça peut aider, j'avais écrit une petite fonction pour représenter une arbo par ici :
http://forum.hardware.fr/hardwaref [...] 4510-1.htm

c'est un peu ce genre là, sauf que c'est l'inverse    
on part d'un structutre linéraire pour la mettre en multidim - enfin moi c'est ce que fait / ce dont j'ai besoin ...

Mouais, ça m'a l'air un poil lourd pour maintenir de gros arbre ton système shakpana non ? Parce que bon, tu ajoutes un élément au début (order = 0) tu modifies TOUT le bazard ?
 
(et l'order de B1 devrait pas valoir 4 dans ton exemple ?)
 
Enfin, ça prouve bien qu'il y a autant de manière de gêrer ça que de personne qui s'y colle

> naceroth
oui bien vu, m'étais planté dans mes copié/collés ... mais cette valuer valeur n'as pas d'importance, tant que tout est ordonné, c'est un champ de la table pour la requete SQL, ici, pour l'exemple
 
> élément au début (order = 0) tu modifies TOUT le bazard
oui, ça donne une requête genre UPDATE table SET order = order + 1 WHERE order > 0
ce qu'il n'y a pas plus terrible, vu que dans mon schema je risque de jamais arriver à plus de, allez disons 30,40,50 entrées et que l'ajout est fait de manière _très_ sporadique
 
> Enfin, ça prouve bien qu'il y a autant de manière de gêrer ça que de personne qui s'y colle
bah oui ... bien dit ...

mais pourquoi donc ? je reprend
à la lecture 1 requête, 1 itération, point barre ...
après je peux pas faire moins, enfin sinon je suis preneur    

ce n'est pas parce que c mysql qui fait les opérations qu'il ne faut pas les compter...
je n'ai pas dit que ce n'etait pas correcte ce que tu as fait loin de là juste moins performant
enfin bref t'es le meilleur

ok, le prends pas comme ça, c'est franchement pas mon propos ...
mais je vois pas en quoi c'est moins performant ... au contraire d'ailleurs ...
 
car la requête dont tu parles (celle que je n'aurais pas compter, mais dont je parle depuis longtemps, celle d'UPDATE order ), tu dois la faire aussi ... dont je cherche toujours ce que je ferais de plus qu'avec la méthode recursive, à part supprimer le récursivité et la table d'adjacence ... y'a strictement rien de plus, donc 1 - 1 + 0 = 0

 
Oui, dans le sens lecture en effet, tout système multi-requête est bon à jeter aux ordures on est d'accord. Par contre, perdre à l'écriture ce que tu gagnes à la lecture, là, je suis moins convaincu. Je prends que l'exemple de ma boite où on a des arbres "simples" dont la seule racine contient dans les 20 branches et pour lesquels on a parfois 7 ou 8 niveaux, mémoriser l'ordre (comme la profondeur d'ailleurs, j'ai même pas réfléchi à comment tu déplaces une branche entière ou, encore plus chiant, une partielle) me semble lourd pour le serveur sql

En pratique, on lit généralement plus souvent qu'on écrit, donc perdre en écriture, c'est moins génant qu'en lecture.
Et pour une arborescence de site, on lit beaucoup plus souvent le menu qu'on ne le modifie.
 
Pour le déplacement d'une branche ou d'une sous-branche, c'est vrai que ca peut sembler lourd, mais en général, on peut s'en sortir en 3 ou 4 requettes si on a bien prévus le truc :

• augmentation de la position des lignes qui se retrouveront situé aprés les lignes qu'on déplace afin de faire de la place afin de permettrre le déplacement de la (sous-)branche
• modification des lignes à déplacer dans l'arborescence (modification d'un certain nombre de champs en fonction de l'organisation)
• pour finir modification de l'ordre d'affichage d'un certain nombre de lignes afin de ne plus avoir de trous dans l'ordre d'affichage

 
En pratique, sur des gros trucs, tu utilises des caches, tu ne t'amuses pas à lire et recréer la structure à chaque accès aux pages...
 

 
Que tu utilises 1, 2 ou X requête(s) ne rend pas moins lourd le fait que tu modifies toute la base ou presque (dans le pire des cas) pour ajouter un et un seul élément, et ce quelque soit la position de l'élément.
 
Prennons un cas basique (je reprend l'exemple de shakpana pour illustrer), tu ajoutes un élément Level 2 Order 3 (à la fin de la première branche donc),  aller modifier dans la foulée des éléments qui n'appartiennent même pas à la même branche me semble très moyen  

Soit l'arborescence
  Accueil
  Php
    Types
      Entier
      Chaine de caractère
    Fonctions
  Javascript
    Intro
    Java / Javascript
 
J'ai décidé de coder l'algo dont je parlais
Je precise que je suis loin de maitriser le php et qu'il y a certainement moyen d'optimiser pas mal d'instructions (concaténation, initialisation du tableau etc) [je code essentiellement en java]
 

 
EXEMPLE D'UTILISATION  
----------------------------------------------------------
 
Arborescence avant insertion
 
02:   Accueil
01:   Php
04:      Types
05:         Entier
06:         Chaine de caractère
03:      Fonctions
07:   Javascript
08:      Intro
09:      Java / Javascript
 
J'insere simultanement les rubriques suivantes (synthaxe: id,nom,id_parent,ordre)  
 
10,isset(),3,1
11,trim(),3,1
12,chop(),3,2
13,Fonction,7,3
 
CELA DONNE
 
Bilan de construction
------------------------------
Opérations: 7 maj de positions
Appel récursif: 15
------------------------------
 
 
Arborescence apres insertions et construction
------------------
02:   Accueil
01:   Php
04:      Types
05:         Entier
06:         Chaine de caractère
03:      Fonctions
11:         trim()
12:         chop()
10:         isset()
07:   Javascript
08:      Intro
09:      Java / Javascript
13:      Fonction

oui d'ailleurs, je pense à inclure un cache XML, un de ces quatres ...

je suis, bien sûr, de ton avis en ce cas, sur une arbo de 200 items, çe devient lourd comme comportement ...
mais en ce cas, je m'interroge grave sur ton système de gestion, comment est géré l'ordre ?
- ordonancement par branche // nan pas valable car retrouves les mêmes limitations pour une branche de 200 items
- par items de même niveau par branche // ya un truc là, mais pas sans données annexes ou sans recursivité, ce qui était en fait mon système original au lieu d'avoir un liste ordonnée, j'avais une liste nivellée (genre : level 0, 1, 2, 3) que où je raccrochait chaque enfant en fonction de sa branche/niveau/parent i.e. à la méthode de Vlad' mais qui avait cette même limitation : l'ordre absolut
- ma, après j'vois pas bien comment gérer autrement cet(te saletée d')orde...

up, modification du script, post ci-dessus
 
shakpana ton algo est performant pour l'ajout d'un unique element, mais des lors ou qd tu veux ajouter plusieurs elements l'algo de parcours est bien meilleur.
 
je cite

 
l'algo en profondeur update au pire (si on ajoute m elements en tete) n+m positions où n=nombre de rubriques dans la base
on peut tres bien construire une arborescence complete de n elements ca fera n+1 appels recursifs et n affectation de positions.
 
ton algo update au pire (si tu ajoutes m elements en tete) (n+1)+(n+2)+....+(n+m) positions  
Pour etre plus clair [update set position = position +1 where position > 0] m fois.
Bref environ n*m mise a jours de positions
tu vois le hic
 
pour résumer:  
si on veut ajouter plusieurs rubriques : insertion utilisant l'algo de parcours.
si on veut ponctuellement ajouter une rubrique à l'arborescence: ton algo.

ok, j'ai bien compris ton idée
 
mais ta parcours_arbo()
tu fais un foreach() qui mène à un sql(UPDATE) pour maintenir ton champ position, donc  
x étant le nombre d'éléments en dessous du point d'insertion,
toi tu fais m+x sql(UPDATE) qui touchent m+x éléments
moi je fait 2 sql(UPDATE) qui touchent en fait m+m+x éléments - cf plus bas pour mon process
attention ! à ce point je ne dis pas mieux ou moins bien ...
car en si on remonte 200 el. de 300 places
je touche 700 el. contre toi qui en touches 500 el.
mais je ne puis dire honnêtemment si  
500 sql_queries pour 500 éléments
est mieux que
2 sql_queries pour 500 + 200 éléments
même si j'ai une grande tendance à penser que 500 appels à une fonction pour 500 opérations SQL c'est plus long que 700 opérations en 2 appels*
*EDIT: toutes ces 2 queries n'affecte qu'un seul champ : "order"
à ce point, je pense qu'un bench va s'imposer, car au final les deux méthodes proposent les mêmes fonctionnalités ...
 
pour décrire ma mise à jour, je la fait ainsi
1. requête de décalage des éléments suivant le point d'insert.
2. requête de décalage des éléments à déplacer
donc en gros, c'est du décalage d'offset ..
au lieu de faire "m*n requêtes", donc pour ça j'ai besoin de connaitre
1. ordre du noeud précédent le point d'insert
2. ordre du 1er el. à déplacer
3. ordre du dernier el. à déplacer (dernier enfant du 1er el. à déplacer)
que j'obtiens par le formulaire de mise à jour
et il n'y a pas de différence entre la maj et l'ajout (sauf les multiples sql(INSERT))
 
donc au final, et comme je le disais dans mon post précédent, et pointé par naceroth, ce qui nous bloque (enfin ce qui bloque ces deux méthodes) c'est la gestion de cet ordre absolut ... mais là je vois pas du tout comment s'en passer ...
 
en tout cas merci de ces échanges, c'est bien cool

tu parles de m insertions d'elements qui repectent tous une propriété essentiellle : elle sont toutes devant toutes les autres (en tete) ca te permet de deplacer de m place  les x elements du dessous. Je t'ai tendu une perche, c'etait pas le bonne exemple en fait.
Disons que tu veux ajouter m elements qui n'ont vraisemblablement rien en commun, tu ne peux donc pas rusé (point d'insertion differents pour chaque element). il faudra que tu ajoutes les m elements un à un en decalant a chaque fois correctement. soit bien cette fois ci m requetes [update set pos =pos + 1 where pos > element dans m]

oui, précisement, je parlais du _déplacement_ d'un branche, vers un autre emplacement ...
donc un UPDATE et non un INSERT
 
> Disons que tu veux ajouter m elements qui n'ont vraisemblablement rien en commun
oui en ce cas je te suis, tu as raison
pour chaque INSERT qui ne constitue pas une branche, je devrais faire mon process complet
 
mais je vois pas la différence fondamentale, car tu as aussi un champ "position" ordre absolut à maintenir pour chaque INSERT - comme ouam, je m'explique :
 
c'est un cas que j'envisage pas dans mon process, chaque INSERT est soit une entrée unique, soit un arbre, mais si je devais l'envisager, j'aurais autant de sql_query que neccessaire ce qui revient à faire pour une insertion de 100 el. à l'offset 100 et 100 el. à l'offset 200 sur une struct de 300 => d'abord 2 UPDATE table SET order = order + 100 + taille_de_l_insert_suivant_en_ordre_inverse WHERE order > point_d_insert_en_cours AND order < ordre_du_dernier_insert - 1 en commençant par le dernier et les 200 INSERT complets
donc le minimum requis sans itération, sans récursion, en 202 requêtes ...
tout ça via une fonction spécifique genre add_multi()
hélas hé-oui, cette fois je touche autant de records que toi, avec beaucoup moins* de requêtes !?!
donc je touche tous les éléments en dessous du premier point d'insert., et tu est obligé le faire aussi car tu dois réécrire ta 'position' ...
* bah oui, là tu en fera 200 + 200
 
donc j'ai bien eu ta perche sur ce coup là ...

moi je parle d'inserer par exemple 100 elements a des offset differents et non pas au meme. donc avec ton algo 100 fois [update set pos=pos +1 where pos > x]  pour a chaque fois decaler de 1 tous les trucs en dessous.
dans cette situation l'algo de parcours fera ca en ((n-position du parent le plus haut)+200) requetes update set position where id=x.
 
Pour etre plus clair et en arrondissant : ca ne revient vraiment pas au meme de faire n requetes qui mettent à jour une unique position et n requetes qui mettent à jour m positons !
 
MISE EN SITUATION
------------------------------
 
ARBORESCENCE DE DEPART
-----------------------------
02:   Accueil
01:   Php
04:      Types
05:         Entier
06:         Chaine de caractère
03:      Fonctions
07:   Javascript
08:      Intro
09:      Java / Javascript
 
INSERTION DES ELEMENTS SUIVANTS
 
10,Fonctions,7,2
11,Blabla,8,1
12,Differences,9,1
12,Maths,10,1
13,random(),12,1
14,round(),12,1
15,Dates,10,2
16,getDate(),15,1
17,getDay(),15,2
 
RESULTAT
----------------------------------
Bilan de construction
 
Opérations: 10 maj de positions
Appel récursif: 18
 
Arborescence
02:   Accueil
01:   Php
04:      Types
05:         Entier
06:         Chaine de caractère
03:      Fonctions
07:   Javascript
08:      Intro
11:         Blabla
10:      Fonctions
15:         Dates
16:            getDate()
17:            getDay()
09:      Java / Javascript
12:         Differences
14:            round()
13:            random()
-----------------------------------------------
 
mais revenons a ton cas particulier (plusieurs ajouts au meme endroit).
 
on est d'accord que pour ton exemple tu fais 2 requetes, la on je fais m requetes.
 
mais il n'y a pas de difference au niveau du nombre de mise a jour de positions
ce n'est parce que c une requete que ca coute 1
qd tu fais un update set pos= pos + y where pos > x, c en fait un boucle de 'update set pos = pos + y' pour les lignes respectant le where donc autant que moi.
 
j'ai bien compris ton argument : une requete qui modifie tout en meme temps est mieux que n requetes qui modifie un seul element c sur!
c pour cela que je dis que dans le cas d'un ajout unique (et aussi je n'y avait pas pensé, de plusieurs ajouts sur un meme point d'insertion ton algo est meilleur. mais des qu'il s'agit d'ajouter des elements a des parents differents c fini.
 
j'ajoute que pour reserrer l'ecart de performance entre ton algo et le mien,dans ce cas precis (ajouts sur meme point d'insertion) on peut mettre a jour les positions a la fin du parcours.
on stocke l'id et sa position dans un tableau et a la fin on met a jour en quelques requetes toutes les positions!
cad par exemple faire 20updates par query. mysql_query(update.....;update.....;......;update...;);
on ferait donc par exemple pour 300updates 15requetes ce qui est tres raisonnable.
 
bref l'ajout sur un meme point d'insertion reste un cas particulier, dans la pratique on veut pouvoir ajouter les elements comme ca nous chante.
donc l'algo de parcours est vraisemblablement l'ideal car polyvalent, il assure une mise a jour coutant au pire n+m mise a jour de positions pour m insertions (ou m est non borné!).
 
tu sais moi j'invente rien, c mon cours d'algorithmie des arbres, le parcours en profondeur est l'algo le meilleur pour travailler sur les arborescences. tu auras beau retourner le truc dans tous les sens, des lors que les ajouts ne touchent pas le meme parent tu ne pourras pas faire mieux
 
je dirai que c fut une sacrée etude!
j'ai revisé mes connaissance en algoritmie avec tout ce travail :p

ok, je reconnais avoir un peu tordu ton argument ... en ne prenant que 2 points d'insert ...    
 
encore une fois mon système utilisait d'abord la méthode récursive, et en me prenant bien la tête, j'ai pondu cette soluce qui m'a permis de réduire drastiquement le nb de lignes de code, et de donc de gagner quelques cycles processeurs non-négligeable ... sans toucher aux fonctionnalités finales
mais effectivement et clairement, ce n'est pas une solution orthodoxe au sens théorique ...

oui, mais comme je te l'ai dis ce n'est pas mon propos de dire qu'elle est meilleur, loin de là, je soutenais juste que cette méthode est aussi valable et qu'elle n'en est pas moins performante, toute choses étant égales par ailleurs (j'aime bien cette phrase vide de sens) elle a ses défauts, mais comme la récursive a les siens ... en tout cas en relation avec des requêtes sql derrière ...
Et pour l'anecdote, moi pas de cours d'algorithmie, me suis formé sur le tas, sans aucun mérite et avec beaucoup de café

bah oui a qui le dis-tu, et je ne desespère pas une fois avoir terminé qlqs projets en cours de faire 2 ptites classes reprenant mon code en cours et un mélange de mon ancien système + tes modifs si neccessaire pour en faire qlq chose d'utile, et pis un peu de benchmark qd même ...
et pour voir si j'arrive à m'affranchir de cet `order` ... advienne que pourra  

tu m'etonnes, moi je cumul l'apprentissage scolaire et personnel.
 

franchement ct pas bete du tout et sans mes cours j'aurais surment fait comme ca.
 

là tu te leurres mais arretons en là pour les chamailleries
 

 
Clair, je suis sur qu'en melangeant le parcours en profondeur recursif, la modelisation en classe, ta structure xml et un feuille xsl ca le ferait bien

<shakpana> j'ai pondu cette soluce
<Vlad'> franchement ct pas bete du tout et sans mes cours j'aurais surment fait comme ca.
mais enfin ?!? je te répètes que ma 1ère méthode était celle que tu as présenté tout le long du thread ...
spa possible, ça ! donc j'ai déjà fait la méthode récursive, là même que la tienne !
 
<shakpana> réduire drastiquement le nb de lignes de code, et de donc de gagner quelques cycles processeurs non-négligeable
<Vlad'> là tu te leurres mais arretons en là pour les chamailleries
mon temps de génération de page est tombé de quelques pourcent pas négligeable ...
donc j'ai _vu_ le bénéfice, et ne me leurre pas sur ce point précis ...
- fait le test de 1000 sql_query sur 1 record contre 1000x1 sql_query sur 1 record, parce que même si tu dis l'avoir compris, je suis pas sûr que tu réalises l'importance de cette nuance, un appel à une fonction est couteux
- la génération de l'arbre* est fait en 5 lignes répéter par n items
- *de plus tu ne gères pas cet arbre : le tableau multidimmensionel; alors c'est le but que je recherche; tu te contentes d'afficher direct la liste avec l'indentation, alors que j'ai besoin de sortir un tableau à n niveaux
 
mais ok restons en là ... sinon on est repartit pour un tour    
 
<shakpana> mon code en cours et un mélange de mon ancien système + tes modifs si neccessaire pour en faire qlq chose d'utile
<Vlad'> Clair, je suis sur qu'en melangeant le parcours en profondeur recursif, la modelisation en classe, ta structure xml et un feuille xsl ca le ferait bien
vi, c'est déjà fait, ma classe actuelle output soit via DOM, soit via à_la_mano, et recursion-free
reste un système de cache XML, et pour XSL à voir ...
mais je sortirais l'essentiel pour en faire deux classes de base lecture/écriture/sortie d'un tableau multidimm./sortie d'une zone de liste HTML <ul><li>/sortie DOM dont une recursive, et l'autre non
 
to be continued ...

 
En simplifiant un max (parce que la recréation de l'arbre passe en partie par des fonctions créées spécialement pour, le tout dans une dll), on se fiche complètement de l'ordre absolu dans la db.
 
Bon, faut remettre ça dans le contexte : un gros arbre qui une fois normalement rempli va subir moins d'insert/delete que de déplacements d'éléments/branches. On s'est donc demander comment optimiser les déplacements et il est assez clair que gérer un ordre absolu est très moyen pour les raisons évoquées plus haut. On a à la place choisi un ordre relatif, certes un poil plus lourd en terme de code à la lecture (difficile à estimer, vu que tout n'est pas du php pur), mais nettement plus souple en mise à jour : si on déplace l'élément X, on doit modifier l'élément qui précède l'ancienne position de X et l'élément qui précède la nouvelle position de X ainsi que X lui même.
 
Pour reprendre partiellement la mise en situation de Vlad' et en tenant compte de l'optimisation de base des insertions, si on devait ajouter en une seule fois les éléments 10, 15, 16 et 17 (la branche Fonctions de Javascript), on aurait 4 inserts et 1 update (pour l'ajout de Fonctions), sauf erreur de ma part.

ah ok, je vois mieux maintenant, merci de ta réponse.
j'avais exploré l'interdépendance un moment, mais apparament pas assez ...    
 
> (...) on aurait 4 inserts et 1 update (...)
et on ne toucherait que 5 éléments ... et 2 pour un déplacement de la même branche ...
 
vi vi vi, ben je vais retourner à mes crayons ...
et je vais poser ça par écrit, pour en sortir ce que j'ai dit, mes ptites classes de gestion ...
naceroth, merci  

naceroth j'ai pas vu trop de quoi tu parlais mais il me semble que ca rejoint un autre idée a laquelle j'ai pensé.
gérer l'ajout, la modification, la suppression et le deplacement avec un graphe.
c'est à dire un objet Rubrique du genre
 
Rubrique
-----------------
int etiquette;
string nom;
Rubrique suivants; //rubriques de meme niveau
Rubrique enfants; //sous rubriques
-----------------
ajouter_enfant()
ajouter_suivant()
exporter_xml()
importer_mysql()
 

edit : les cycles sont utiles que si on veut ordonné les rubriques de meme niveaul
 
pour
Accueil
Php
  Types
  Fonctions
Javascript
  Types
  Fonctions
 
On sauvegarderait uniquement chaque rubrique avec leurs etiquette, nom et parent dans la bd
une methode importerait les données pour creer le graphe.
pour terminer une methode creerait le xml