Supposons que vous ayez une table plate qui stocke une hiérarchie d'arbre ordonnée:
Id Name ParentId Order
1 'Node 1' 0 10
2 'Node 1.1' 1 10
3 'Node 2' 0 20
4 'Node 1.1.1' 2 10
5 'Node 2.1' 3 10
6 'Node 1.2' 1 20
Voici un diagramme, où nous en avons [id] Name
. Le nœud racine 0 est fictif.
[0] RACINE / \ [1] Nœud 1 [3] Nœud 2 / \ \ [2] Noeud 1.1 [6] Noeud 1.2 [5] Noeud 2.1 / [4] Noeud 1.1.1
Quelle approche minimaliste utiliseriez-vous pour produire cela en HTML (ou texte, d'ailleurs) sous la forme d'un arbre correctement ordonné et correctement en retrait?
Supposons en outre que vous n'avez que des structures de données de base (tableaux et hashmaps), pas d'objets fantaisistes avec des références parent / enfants, pas d'ORM, pas de framework, juste vos deux mains. Le tableau est représenté comme un ensemble de résultats, auquel on peut accéder de manière aléatoire.
Le pseudo-code ou l'anglais simple est correct, c'est une question purement conceptuelle.
Question bonus: Existe-t-il un moyen fondamentalement meilleur de stocker une structure arborescente comme celle-ci dans un SGBDR?
MODIFICATIONS ET ADDITIONS
Pour répondre à la question d'un intervenant ( Mark Bessey ): Un nœud racine n'est pas nécessaire, car il ne sera jamais affiché de toute façon. ParentId = 0 est la convention pour exprimer "ce sont des niveaux supérieurs". La colonne Ordre définit comment les nœuds avec le même parent vont être triés.
Le "jeu de résultats" dont j'ai parlé peut être décrit comme un tableau de hashmaps (pour rester dans cette terminologie). Car mon exemple était censé être déjà là. Certaines réponses vont plus loin et le construisent d'abord, mais ça va.
L'arbre peut être arbitrairement profond. Chaque nœud peut avoir N enfants. Cependant, je n'avais pas exactement une arborescence de "millions d'entrées" en tête.
Ne confondez pas mon choix de nom de nœud ('Node 1.1.1') avec quelque chose sur lequel compter. Les nœuds pourraient également être appelés «Frank» ou «Bob», aucune structure de dénomination n'est impliquée, c'était simplement pour la rendre lisible.
J'ai publié ma propre solution pour que vous puissiez la mettre en pièces.
Réponses:
Maintenant que MySQL 8.0 prend en charge les requêtes récursives , nous pouvons dire que toutes les bases de données SQL populaires prennent en charge les requêtes récursives dans la syntaxe standard.
J'ai testé les requêtes récursives dans MySQL 8.0 dans ma présentation Recursive Query Throwdown en 2017.
Voici ma réponse originale de 2008:
Il existe plusieurs façons de stocker des données arborescentes dans une base de données relationnelle. Ce que vous montrez dans votre exemple utilise deux méthodes:
Une autre solution est appelée ensembles imbriqués et peut également être stockée dans la même table. Lisez " Arbres et hiérarchies en SQL pour Smarties " par Joe Celko pour plus d'informations sur ces conceptions.
Je préfère généralement une conception appelée Closure Table (aka "Adjacency Relation") pour stocker des données arborescentes. Il nécessite une autre table, mais interroger les arbres est assez facile.
Je couvre la table de fermeture dans ma présentation Modèles de données hiérarchiques avec SQL et PHP et dans mon livre Antipatterns SQL: éviter les pièges de la programmation de base de données .
Stockez tous les chemins dans la table de fermeture, où il existe une ascendance directe d'un nœud à un autre. Inclure une ligne pour chaque nœud pour se référencer. Par exemple, en utilisant l'ensemble de données que vous avez montré dans votre question:
Vous pouvez maintenant obtenir un arbre commençant au nœud 1 comme ceci:
La sortie (dans le client MySQL) ressemble à ceci:
En d'autres termes, les nœuds 3 et 5 sont exclus, car ils font partie d'une hiérarchie distincte, ne descendant pas du nœud 1.
Re: commentaire d'e-satis sur les enfants immédiats (ou le parent immédiat). Vous pouvez ajouter une
path_length
colonne " " pourClosureTable
faciliter la recherche spécifique d'un enfant ou d'un parent immédiat (ou de toute autre distance).Ensuite, vous pouvez ajouter un terme dans votre recherche pour interroger les enfants immédiats d'un nœud donné. Ce sont des descendants dont le
path_length
1.Commentaire de @ashraf: "Que diriez-vous de trier tout l'arbre [par nom]?"
Voici un exemple de requête pour renvoyer tous les nœuds qui sont des descendants du nœud 1, les joindre à la FlatTable qui contient d'autres attributs de nœud tels que
name
et trier par nom.Re commentaire de @Nate:
Un utilisateur a suggéré une modification aujourd'hui. Les modérateurs ont approuvé la modification, mais je l'inverse.
L'édition a suggéré que l'ORDRE PAR dans la dernière requête ci-dessus soit
ORDER BY b.path_length, f.name
, probablement pour s'assurer que la commande correspond à la hiérarchie. Mais cela ne fonctionne pas, car il ordonnerait "Node 1.1.1" après "Node 1.2".Si vous voulez que le classement corresponde à la hiérarchie de manière sensée, c'est possible, mais pas simplement en triant par la longueur du chemin. Par exemple, voir ma réponse à la base de données hiérarchique MySQL Closure Table - Comment extraire les informations dans le bon ordre .
la source
parent_id
) n'a qu'une seule ligne pour exprimer chaque relation parent-enfant, mais la table de fermeture en a plusieurs.Si vous utilisez des ensembles imbriqués (parfois appelés Traversée d'arbre de précommande modifiée), vous pouvez extraire la totalité de la structure de l'arborescence ou tout sous-arbre dans celle-ci dans un ordre d'arborescence avec une seule requête, au prix d'insertions plus coûteuses, car vous devez gérer les colonnes qui décrivent un chemin dans l'ordre à travers la structure arborescente.
Pour django-mptt , j'ai utilisé une structure comme celle-ci:
Qui décrit un arbre qui ressemble à ceci (avec
id
représentant chaque élément):Ou, sous forme de diagramme d'ensemble imbriqué qui rend plus évident le fonctionnement des valeurs
lft
etrght
:Comme vous pouvez le voir, pour obtenir la sous-arborescence entière pour un nœud donné, dans l'ordre de l'arborescence, vous devez simplement sélectionner toutes les lignes qui ont
lft
et desrght
valeurs entre ses valeurslft
etrght
. Il est également simple de récupérer l'arbre des ancêtres pour un nœud donné.La
level
colonne est un peu de dénormalisation pour plus de commodité et latree_id
colonne vous permet de redémarrer la numérotationlft
etrght
pour chaque nœud de niveau supérieur, ce qui réduit le nombre de colonnes affectées par les insertions, les déplacements et les suppressions, car les colonneslft
etrght
doivent être ajustés en conséquence lorsque ces opérations ont lieu afin de créer ou de combler des lacunes. J'ai pris quelques notes de développement au moment où j'essayais de faire le tour des requêtes requises pour chaque opération.En termes de travail avec ces données pour afficher une arborescence, j'ai créé une
tree_item_iterator
fonction utilitaire qui, pour chaque nœud, devrait vous donner suffisamment d'informations pour générer le type d'affichage que vous souhaitez.Plus d'informations sur MPTT:
la source
lft
etrght
pour les noms de colonne, je veux dire combien de caractères nous n'avons pas eu à taper? une?!C'est une question assez ancienne, mais comme il y a beaucoup de points de vue, je pense qu'il vaut la peine de présenter une solution alternative et, à mon avis, très élégante.
Afin de lire une arborescence, vous pouvez utiliser des expressions de table communes récursives (CTE). Il donne la possibilité de récupérer la structure d'arbre entière à la fois, d'avoir les informations sur le niveau du nœud, son nœud parent et l'ordre dans les enfants du nœud parent.
Permettez-moi de vous montrer comment cela fonctionnerait dans PostgreSQL 9.1.
Créer une structure
Rédiger une requête
Voici les résultats:
Les nœuds d'arbre sont classés par niveau de profondeur. Dans la sortie finale, nous les présenterions dans les lignes suivantes.
Pour chaque niveau, ils sont classés par parent_id et node_order dans le parent. Cela nous indique comment les présenter dans le nœud de liaison de sortie au parent dans cet ordre.
Ayant une telle structure, il ne serait pas difficile de faire une très belle présentation en HTML.
Les CTE récursifs sont disponibles dans PostgreSQL, IBM DB2, MS SQL Server et Oracle .
Si vous souhaitez en savoir plus sur les requêtes SQL récursives, vous pouvez soit consulter la documentation de votre SGBD préféré, soit lire mes deux articles couvrant ce sujet:
la source
Depuis Oracle 9i, vous pouvez utiliser CONNECT BY.
Depuis SQL Server 2005, vous pouvez utiliser une expression de table commune récursive (CTE).
Les deux produiront les résultats suivants.
la source
La réponse de Bill est plutôt bonne, cette réponse y ajoute des choses qui me font souhaiter des réponses filetées SO supportées.
Quoi qu'il en soit, je voulais prendre en charge l'arborescence et la propriété Order. J'ai inclus une propriété unique dans chaque noeud appelé
leftSibling
qui fait la même choseOrder
que pour la question d'origine (maintenir l'ordre de gauche à droite).Plus de détails et de code SQL sur mon blog .
Merci Bill, votre réponse a été utile pour commencer!
la source
Etant donné le choix, j'utiliserais des objets. Je créerais un objet pour chaque enregistrement où chaque objet a une
children
collection et les stockerais tous dans un tableau assoc (/ table de hachage) où l'ID est la clé. Et parcourez la collection une fois, en ajoutant les enfants aux champs enfants concernés. Facile.Mais parce que vous n'êtes pas amusant en restreignant l'utilisation de bons POO, je répéterais probablement en fonction de:
Edit: c'est similaire à quelques autres entrées, mais je pense que c'est légèrement plus propre. Une chose que j'ajouterai: c'est extrêmement intensif en SQL. C'est méchant . Si vous avez le choix, suivez la route OOP.
la source
Cela a été écrit rapidement, et n'est ni joli ni efficace (en plus il a beaucoup de boîtes automatiques, la conversion entre
int
etInteger
est ennuyeux!), Mais cela fonctionne.Cela brise probablement les règles puisque je crée mes propres objets mais bon je fais ça comme un détournement du vrai travail :)
Cela suppose également que le resultSet / table est complètement lu dans une sorte de structure avant de commencer à construire des nœuds, ce qui ne serait pas la meilleure solution si vous avez des centaines de milliers de lignes.
la source
Il existe de très bonnes solutions qui exploitent la représentation interne des index sql. Ceci est basé sur de grandes recherches effectuées vers 1998.
Voici un exemple de table (en mysql).
Les seuls champs nécessaires à la représentation arborescente sont:
Voici un exemple de population à 24 nœuds, ordonné par tw:
Chaque résultat d'arbre peut être fait de manière non récursive. Par exemple, pour obtenir une liste des ancêtres du nœud à tw = '22 '
Les ancêtres
Les frères et sœurs et les enfants sont triviaux - utilisez simplement l'ordre des champs pa par tw.
Descendance
Par exemple, l'ensemble (branche) de nœuds enracinés à tw = 17.
Notes complémentaires
Cette méthodologie est extrêmement utile lorsque le nombre de lectures est beaucoup plus élevé qu'il n'y a d'insertions ou de mises à jour.
Étant donné que l'insertion, le déplacement ou la mise à jour d'un nœud dans l'arborescence nécessite que l'arborescence soit ajustée, il est nécessaire de verrouiller la table avant de commencer l'action.
Le coût d'insertion / suppression est élevé car les valeurs d'index tw et de sz (taille de branche) devront être mises à jour sur tous les nœuds après le point d'insertion et pour tous les ancêtres respectivement.
Le déplacement de branche implique de déplacer la valeur tw de la branche hors de portée, il est donc également nécessaire de désactiver les contraintes de clé étrangère lors du déplacement d'une branche. Il y a, essentiellement, quatre requêtes nécessaires pour déplacer une branche:
Ajuster les requêtes d'arborescence
L'ouverture / fermeture des lacunes dans l'arborescence est une sous-fonction importante utilisée par les méthodes de création / mise à jour / suppression, donc je l'inclus ici.
Nous avons besoin de deux paramètres - un indicateur indiquant si nous réduisons ou augmentons ou non l'index tw du nœud. Ainsi, par exemple tw = 18 (qui a une taille de branche de 5). Supposons que nous réduisions (supprimions tw) - cela signifie que nous utilisons «-» au lieu de «+» dans les mises à jour de l'exemple suivant.
Nous utilisons d'abord une fonction ancêtre (légèrement modifiée) pour mettre à jour la valeur sz.
Ensuite, nous devons ajuster le tw pour ceux dont le tw est supérieur à la branche à supprimer.
Ensuite, nous devons ajuster le parent pour ceux dont le tw de pa est supérieur à la branche à supprimer.
la source
En supposant que vous savez que les éléments racine sont nuls, voici le pseudocode à afficher en texte:
la source
Vous pouvez émuler n'importe quelle autre structure de données avec une table de hachage, donc ce n'est pas une terrible limitation. De haut en bas, vous créez une table de hachage pour chaque ligne de la base de données, avec une entrée pour chaque colonne. Ajoutez chacun de ces hashmaps à un hashmap "maître", basé sur l'identifiant. Si un nœud a un "parent" que vous n'avez pas encore vu, créez une entrée d'espace réservé pour lui dans la table de hachage principale et remplissez-la lorsque vous voyez le nœud réel.
Pour l'imprimer, effectuez un simple passage en profondeur d'abord à travers les données, en gardant une trace du niveau de retrait en cours de route. Vous pouvez rendre cela plus facile en conservant une entrée "enfants" pour chaque ligne et en la remplissant lorsque vous numérisez les données.
Quant à savoir s'il existe une "meilleure" façon de stocker un arbre dans une base de données, cela dépend de la façon dont vous allez utiliser les données. J'ai vu des systèmes qui avaient une profondeur maximale connue qui utilisaient une table différente pour chaque niveau de la hiérarchie. Cela a beaucoup de sens si les niveaux dans l'arbre ne sont pas tout à fait équivalents après tout (les catégories de niveau supérieur étant différentes des feuilles).
la source
Si des cartes ou des tableaux de hachage imbriqués peuvent être créés, je peux simplement descendre le tableau depuis le début et ajouter chaque élément au tableau imbriqué. Je dois tracer chaque ligne jusqu'au nœud racine afin de savoir à quel niveau du tableau imbriqué insérer. Je peux utiliser la mémorisation pour ne pas avoir à rechercher le même parent encore et encore.
Edit: Je voudrais d'abord lire la table entière dans un tableau, donc il ne demandera pas la base de données à plusieurs reprises. Bien sûr, cela ne sera pas pratique si votre table est très grande.
Une fois que la structure est construite, je dois d'abord la parcourir en profondeur et imprimer le code HTML.
Il n'y a pas de meilleur moyen fondamental de stocker ces informations à l'aide d'une seule table (je peux me tromper cependant;), et j'aimerais voir une meilleure solution). Cependant, si vous créez un schéma pour utiliser des tables de base de données créées dynamiquement, vous avez ouvert un tout nouveau monde au prix de la simplicité et du risque d'enfer SQL;).
la source
Si les éléments sont dans l'ordre de l'arborescence, comme indiqué dans votre exemple, vous pouvez utiliser quelque chose comme l'exemple Python suivant:
Cela permet de conserver une pile représentant la position actuelle dans l'arborescence. Pour chaque élément du tableau, il affiche les éléments de la pile (fermant les divisions correspondantes) jusqu'à ce qu'il trouve le parent de l'élément en cours. Ensuite, il sort le début de ce nœud et le pousse vers la pile.
Si vous souhaitez générer l'arborescence à l'aide d'éléments en retrait plutôt que imbriqués, vous pouvez simplement ignorer les instructions d'impression pour imprimer les divs et imprimer un nombre d'espaces égal à un multiple de la taille de la pile avant chaque élément. Par exemple, en Python:
Vous pouvez également facilement utiliser cette méthode pour construire un ensemble de listes ou de dictionnaires imbriqués.
Edit: Je vois d'après votre clarification que les noms n'étaient pas destinés à être des chemins de noeud. Cela suggère une approche alternative:
Cela construit un arbre de tableaux de tuples (!). idx [0] représente la ou les racines de l'arbre. Chaque élément d'un tableau est un 2-tuple composé du nœud lui-même et d'une liste de tous ses enfants. Une fois construit, vous pouvez conserver idx [0] et ignorer idx, sauf si vous souhaitez accéder aux nœuds par leur ID.
la source
Pour étendre la solution SQL de Bill, vous pouvez essentiellement faire de même en utilisant un tableau plat. De plus, si vos chaînes ont toutes la même longueur et que votre nombre maximum d'enfants est connu (par exemple dans un arbre binaire), vous pouvez le faire en utilisant une seule chaîne (tableau de caractères). Si vous avez un nombre arbitraire d'enfants, cela complique un peu les choses ... Je devrais vérifier mes anciennes notes pour voir ce qui peut être fait.
Ensuite, en sacrifiant un peu de mémoire, surtout si votre arbre est clairsemé et / ou non équilibré, vous pouvez, avec un peu de calcul d'index, accéder à toutes les chaînes de façon aléatoire en stockant votre arbre, largeur d'abord dans le tableau comme ceci (pour un binaire arbre):
vous connaissez la longueur de votre chaîne, vous le savez
Je suis au travail maintenant, je ne peux donc pas y consacrer beaucoup de temps, mais avec intérêt, je peux récupérer un peu de code pour le faire.
Nous avons l'habitude de le faire pour rechercher dans des arbres binaires faits de codons d'ADN, un processus a construit l'arbre, puis nous l'avons aplati pour rechercher des modèles de texte et lorsqu'il est trouvé, bien que les mathématiques d'index (inverser d'en haut) nous récupérons le nœud ... très rapide et efficace, notre arbre avait rarement des nœuds vides, mais nous pouvions rechercher des gigaoctets de données en un tournemain.
la source
Pensez à utiliser des outils nosql comme neo4j pour les structures hiérarchiques. par exemple, une application en réseau comme linkedin utilise couchbase (une autre solution nosql)
Mais utilisez nosql uniquement pour les requêtes au niveau du magasin de données et non pour stocker / gérer les transactions
la source