Conversation
precedente ou
suivante
Stocker une b-arborescence dans une base mysql
Envoyé par:
Fifre
Bonjour tout le monde,
Je cherche a stocker un b-arbre dans une base de donnée mysql. (un arbre dont chaque sommet peut avoir de 0 a b descendant... je sais pas si je me fais comprendre :/)
Pour ca j'ai pensé principalement a 2 solutions :
1 Une grosse table dans lequel les sommet aurait un champ 'prec' referencant le sommet précedent,
2 ou alors organiser des 'niveaux', la racine est le niveau 0, chaque sommet suivant la racine et stocké dans une autre table appelée niveau 1 , etc etc ... chaque table de niveau est crée selon le besoin (si un sommet est rajoute dans un autre niveau, la table niveau est créée
La premiere solution donne une tres grosse table quand l'arbre grossi (tout est stocké dedans) et la seconde par contre me donne plein de petite table (une par 'niveau')... Et la question est : c'est quoi le mieux pour mysql ???? qu'en penser vous ? si vous avez une idée
Merci !
[PS private : morgan, c'est pour un projet dont on avait parlé tous les deux, et que je reprend a 0]
Je cherche a stocker un b-arbre dans une base de donnée mysql. (un arbre dont chaque sommet peut avoir de 0 a b descendant... je sais pas si je me fais comprendre :/)
Pour ca j'ai pensé principalement a 2 solutions :
1 Une grosse table dans lequel les sommet aurait un champ 'prec' referencant le sommet précedent,
2 ou alors organiser des 'niveaux', la racine est le niveau 0, chaque sommet suivant la racine et stocké dans une autre table appelée niveau 1 , etc etc ... chaque table de niveau est crée selon le besoin (si un sommet est rajoute dans un autre niveau, la table niveau est créée
La premiere solution donne une tres grosse table quand l'arbre grossi (tout est stocké dedans) et la seconde par contre me donne plein de petite table (une par 'niveau')... Et la question est : c'est quoi le mieux pour mysql ???? qu'en penser vous ? si vous avez une idée
Merci !
[PS private : morgan, c'est pour un projet dont on avait parlé tous les deux, et que je reprend a 0]
Poste le Tuesday 11 January 2005 14:43:25
Re: Stocker une b-arborescence dans une base mysql
Envoyé par:
Morgan
Salut Fifre
Un avis comme cela, sans vraiment avoir réfléchi au problème, il y a peut-être mieux mais cela me semble cohérent:
La première solution me semble un peu bourrin (pas assez de séparation des données: tu risques de compliquer les requêtes)
La seconde solution va provoquer l'existence d'une multitude de petites tables et alourdir la base.
Une solution intermédiaire serait à mon avis 2 tables: la première référencerait chaque arbre. La seconde, les messages avec 2 clés: une primaire: id unique obligatoire, et une clef secondaire qui ferait référence à la clef primaire de la première table, ainsi que deux champs, l'un permettant de savoir à quelle branche on a à faire, et le second, sa position dans la branche.
De cette façon, l'affichage des partie de l'arborescence ne demanderait en php que 2 requêtes sql, l'ordre d'affichage étant déterminé par un order by sur le champ indiquant la position dans la branche.
Voilà, c'est la première idée qui me vient pour ce genre de traitement, à discuter probablement ...
___________________________________________________
L'interface chaise-clavier se débuggue elle aussi...
Un avis comme cela, sans vraiment avoir réfléchi au problème, il y a peut-être mieux mais cela me semble cohérent:
La première solution me semble un peu bourrin (pas assez de séparation des données: tu risques de compliquer les requêtes)
La seconde solution va provoquer l'existence d'une multitude de petites tables et alourdir la base.
Une solution intermédiaire serait à mon avis 2 tables: la première référencerait chaque arbre. La seconde, les messages avec 2 clés: une primaire: id unique obligatoire, et une clef secondaire qui ferait référence à la clef primaire de la première table, ainsi que deux champs, l'un permettant de savoir à quelle branche on a à faire, et le second, sa position dans la branche.
De cette façon, l'affichage des partie de l'arborescence ne demanderait en php que 2 requêtes sql, l'ordre d'affichage étant déterminé par un order by sur le champ indiquant la position dans la branche.
Voilà, c'est la première idée qui me vient pour ce genre de traitement, à discuter probablement ...
___________________________________________________
L'interface chaise-clavier se débuggue elle aussi...
Poste le Tuesday 11 January 2005 15:05:49
Re: Stocker une b-arborescence dans une base mysql
Envoyé par:
Fifre
Citation
Morgan
la première référencerait chaque arbre. La
seconde, les messages avec 2 clés: une primaire:
id unique obligatoire, et une clef secondaire qui
ferait référence à la clef primaire de la première
table, ainsi que deux champs, l'un permettant de
savoir à quelle branche on a à faire, et le
second, sa position dans la branche.
En fait, je ne comprend pas 'la premiere referencerait chaque arbre' : je ne veux stocker qu'un arbre ... Et une autre précision : quand tu parles de branche, c'est ce que j'appelle 'niveau' dans mon message ou pas du tout ? Je comprends vite mais il faut m'expliquer longtemps :p
Poste le Tuesday 11 January 2005 15:16:19
Re: Stocker une b-arborescence dans une base mysql
Envoyé par:
Morgan
une seule table ? C'est moi qui n'ait pas bien compris le projet alors... il me semblait qu'il fallait plusieurs arbres (un par histoire).
ce que tu appelles niveau, c'est ce que moi, j'ai appelé "position dans la branche". Mais s'il n'y a qu'une seule table, ma proposition est du même ordre que la tienne (la seconde), sauf que tu identifies les messages en fonction de la "branche" (de l'arbre, pense à l'arborescence de fichiers linux) et non en fonction du niveau.
En fait, je crois qu'il faut que tu m'expliques plus en détail (à moi aussi, des fois, il faut m'expliquer longtemps!).
___________________________________________________
L'interface chaise-clavier se débuggue elle aussi...
ce que tu appelles niveau, c'est ce que moi, j'ai appelé "position dans la branche". Mais s'il n'y a qu'une seule table, ma proposition est du même ordre que la tienne (la seconde), sauf que tu identifies les messages en fonction de la "branche" (de l'arbre, pense à l'arborescence de fichiers linux) et non en fonction du niveau.
En fait, je crois qu'il faut que tu m'expliques plus en détail (à moi aussi, des fois, il faut m'expliquer longtemps!).
___________________________________________________
L'interface chaise-clavier se débuggue elle aussi...
Poste le Tuesday 11 January 2005 15:36:30
Re: Stocker une b-arborescence dans une base mysql
Envoyé par:
Morgan
Dans ce cas, je maintiens la proposition que je te faisais dans mon premier post mais avec une seule table (la seconde). Une ligne pour chaque message avec un id unique, un champ pour indiquer la 'branche' (la clause where), un champ pour indiquer le 'niveau' (la clause order by).
Ceci pour cette raison que si tu prévois plusieurs tables, il faut penser que tu vas devoir construire ta requète en fonction du niveau et de la branche, donc en joignant les tables ou en faisant des requêtes multiples. Les requêtes vers le SGBD risquent à terme d'être trop nombreuses et de surcharger le serveur, sans compter les difficultés pour la maintenance du code.
___________________________________________________
L'interface chaise-clavier se débuggue elle aussi...
Ceci pour cette raison que si tu prévois plusieurs tables, il faut penser que tu vas devoir construire ta requète en fonction du niveau et de la branche, donc en joignant les tables ou en faisant des requêtes multiples. Les requêtes vers le SGBD risquent à terme d'être trop nombreuses et de surcharger le serveur, sans compter les difficultés pour la maintenance du code.
___________________________________________________
L'interface chaise-clavier se débuggue elle aussi...
Poste le Tuesday 11 January 2005 15:53:11
Re: Stocker une b-arborescence dans une base mysql
Envoyé par:
Sve@r
A mon avis ya pas à discuter. Un arbre c'est un élément pointant vers plusieurs éléments semblables à lui-même (fils) et, éventuellement, pointant vers un élément particulier (père).
Une table en BDD est une structure servant à stocker des éléments de même nature. Il serait inconcevable (du point de vue "BDD") de stocker ton arbre dans "x" tables.
La meilleure solution se fait en 2 tables
La première référence chaque élément et les données associées
Exemple (pour un arbre stockant des personnes)
- index
- Nom
- Prénom
- Age
La seconde référence chaque lien entre 2 éléments
Exemple (suite)
- indexCourant
- indexFils
Une table en BDD est une structure servant à stocker des éléments de même nature. Il serait inconcevable (du point de vue "BDD") de stocker ton arbre dans "x" tables.
La meilleure solution se fait en 2 tables
La première référence chaque élément et les données associées
Exemple (pour un arbre stockant des personnes)
- index
- Nom
- Prénom
- Age
La seconde référence chaque lien entre 2 éléments
Exemple (suite)
- indexCourant
- indexFils
Poste le Tuesday 11 January 2005 22:26:41
Re: Stocker une b-arborescence dans une base mysql
Envoyé par:
Fifre
Sve@r, je viens de relire ton post et :
tu voulais pas dire indexPere par hasard ? (chaque fils n'a qu'un pere ... alors qu'un pere a plein de fils, ce qui entraine un champ soit multiple ( 2,3,4,8,9,45 <- liste des fils) soit plein de champ fils1, fils2 etc .. ce qui est pas tres joli quand meme )
Citation
auteur
La seconde référence chaque lien entre 2 éléments
Exemple (suite)
- indexCourant
- indexFils
tu voulais pas dire indexPere par hasard ? (chaque fils n'a qu'un pere ... alors qu'un pere a plein de fils, ce qui entraine un champ soit multiple ( 2,3,4,8,9,45 <- liste des fils) soit plein de champ fils1, fils2 etc .. ce qui est pas tres joli quand meme
)Poste le Thursday 13 January 2005 18:08:51
Re: Stocker une b-arborescence dans une base mysql
Envoyé par:
Sve@r
Non, non, non. Exemple concret: La mère de toto à 3 enfants: Pim, Pam et... Toto
Stockage dans la BDD
Table "personne" avec les colonnes (index, nom, age, commentaire)
1 - Maman - 45 - "Maman de tout le monde"
2 - Pim - 12 - "Enfant de la maman"
3 - Pam - 13 - "Autre enfant"
4 - Toto - 25 - "Il aurait pu se nommer Poum"
Table "lien" avec les colonnes (indexCourant, indexFils)
1 - 2
1 - 3
1 - 4
Evidemment il y a redondance mais la redondance est minime (elle ne concerne que l'indexCourant)
Tu veux tous les fils de la maman avec un BDD qui n'accepte pas les requètes imbriquées (MySQL version GPL par exemple)
a) select index from personne where nom='maman' (résultat à stocker dans "$index")
b) select indexFils from lien where indexCourant=$index (résultat à stocker dans "$fils")
c) select * from personne where index in $fils
Tu veux tous les fils de la maman avec un BDD qui accepte les requètes imbriquées (MySQL payante ou pgSQL par exemple)
=> select * from personne where index in (select indexFils from lien where indexCourant in (select index from personne where nom='maman'))
Tu veux le père de "Toto" avec un SGBD sans requètes imbriquées
a) select index from personne where nom='Toto' (résultat à stocker dans "$index")
b) select indexCourant from lien where indexFils=$index (résultat à stocker dans "$pere")
c) select * from personne where index in $pere
Tu veux le père de "Toto" avec un BDD qui accepte les requètes imbriquées
=> select * from personne where index in (select indexCourant from lien where indexFils in (select index from personne where nom='Toto'))
Tu vois le truc ???
Stockage dans la BDD
Table "personne" avec les colonnes (index, nom, age, commentaire)
1 - Maman - 45 - "Maman de tout le monde"
2 - Pim - 12 - "Enfant de la maman"
3 - Pam - 13 - "Autre enfant"
4 - Toto - 25 - "Il aurait pu se nommer Poum"
Table "lien" avec les colonnes (indexCourant, indexFils)
1 - 2
1 - 3
1 - 4
Evidemment il y a redondance mais la redondance est minime (elle ne concerne que l'indexCourant)
Tu veux tous les fils de la maman avec un BDD qui n'accepte pas les requètes imbriquées (MySQL version GPL par exemple)
a) select index from personne where nom='maman' (résultat à stocker dans "$index")
b) select indexFils from lien where indexCourant=$index (résultat à stocker dans "$fils")
c) select * from personne where index in $fils
Tu veux tous les fils de la maman avec un BDD qui accepte les requètes imbriquées (MySQL payante ou pgSQL par exemple)
=> select * from personne where index in (select indexFils from lien where indexCourant in (select index from personne where nom='maman'))
Tu veux le père de "Toto" avec un SGBD sans requètes imbriquées
a) select index from personne where nom='Toto' (résultat à stocker dans "$index")
b) select indexCourant from lien where indexFils=$index (résultat à stocker dans "$pere")
c) select * from personne where index in $pere
Tu veux le père de "Toto" avec un BDD qui accepte les requètes imbriquées
=> select * from personne where index in (select indexCourant from lien where indexFils in (select index from personne where nom='Toto'))
Tu vois le truc ???
Poste le Friday 14 January 2005 12:36:48
Ce forum !
Stocker une b-arborescence dans une base mysql
Pour poser vos questions sur les scripts shell, le Perl, le C, etc... Attention : nous ne sommes pas des spécialistes du dev, ce forum est juste pour de petites aides ponctuelles concernant le développement et les outils de développement.
Sauf mention contraire, les documentations publiées sont sous licence Creative-Commons