Quelle serait la meilleure façon d'implémenter une structure de données arborescente personnalisable (c'est-à-dire une arborescence avec un nombre inconnu de niveaux) dans une base de données?
Je l'ai fait une fois avant d'utiliser une table avec une clé étrangère pour elle-même.
Quelles autres implémentations pourriez-vous voir, et cette implémentation a-t-elle un sens?
sql
database-design
tree
CodeMonkey1313
la source
la source
Réponses:
Vous mentionnez le plus couramment implémenté, qui est la liste de contiguïté: https://blogs.msdn.microsoft.com/mvpawardprogram/2012/06/25/hierarchies-convert-adjacency-list-to-nested-sets
Il existe également d'autres modèles, notamment des chemins matérialisés et des ensembles imbriqués: http://communities.bmc.com/communities/docs/DOC-9902
Joe Celko a écrit un livre sur ce sujet, qui est une bonne référence d'un point de vue SQL général (il est mentionné dans le lien de l'article imbriqué ci-dessus).
En outre, Itzik Ben-Gann a un bon aperçu des options les plus courantes dans son livre "Inside Microsoft SQL Server 2005: T-SQL Querying".
Les principaux éléments à prendre en compte lors du choix d'un modèle sont:
1) Fréquence du changement de structure - à quelle fréquence la structure réelle de l'arbre change. Certains modèles offrent de meilleures caractéristiques de mise à jour de la structure. Il est cependant important de séparer les changements de structure des autres changements de données. Par exemple, vous souhaiterez peut-être modéliser l'organigramme d'une entreprise. Certaines personnes modéliseront cela comme une liste de contiguïté, en utilisant l'ID d'employé pour lier un employé à son superviseur. Il s'agit généralement d'une approche sous-optimale. Une approche qui fonctionne souvent mieux consiste à modéliser la structure organisationnelle séparément des employés eux-mêmes, et à maintenir l'employé en tant qu'attribut de la structure. De cette façon, lorsqu'un employé quitte l'entreprise, la structure organisationnelle elle-même n'a pas besoin d'être modifiée, juste l'association avec l'employé qui est parti.
2) L'arbre est-il lourd en écriture ou en lecture - certaines structures fonctionnent très bien lors de la lecture de la structure, mais entraînent une surcharge supplémentaire lors de l'écriture dans la structure.
3) Quels types d'informations devez-vous obtenir de la structure? Certaines structures excellent à fournir certains types d'informations sur la structure. Les exemples incluent la recherche d'un nœud et de tous ses enfants, la recherche d'un nœud et de tous ses parents, la recherche du nombre de nœuds enfants remplissant certaines conditions, etc. Vous devez savoir quelles informations seront nécessaires à partir de la structure pour déterminer la structure qui conviendra le mieux vos besoins.
la source
Jetez un œil à la gestion des données hiérarchiques dans MySQL . Il aborde deux approches pour stocker et gérer des données hiérarchiques (arborescentes) dans une base de données relationnelle.
La première approche est le modèle de liste de contiguïté, ce que vous décrivez essentiellement: avoir une clé étrangère qui fait référence à la table elle-même. Bien que cette approche soit simple, elle peut être très inefficace pour certaines requêtes, comme la construction de l'arborescence entière.
La deuxième approche abordée dans l'article est le modèle d'ensemble imbriqué. Cette approche est beaucoup plus efficace et flexible. Reportez-vous à l'article pour obtenir des explications détaillées et des exemples de requêtes.
la source
Si vous devez utiliser Relational DataBase pour organiser la structure de données arborescente, Postgresql a un module ltree sympa qui fournit un type de données pour représenter les étiquettes des données stockées dans une structure arborescente hiérarchique. Vous pouvez obtenir l'idée à partir de là (pour plus d'informations, voir: http://www.postgresql.org/docs/9.0/static/ltree.html )
En commun, LDAP est utilisé pour organiser les enregistrements dans une structure hiérarchique.
la source
Avoir une table avec une clé étrangère pour elle-même a du sens pour moi.
Vous pouvez ensuite utiliser une expression de table commune dans SQL ou l'instruction précédente connect by dans Oracle pour créer votre arborescence.
la source
Fantastique collection de fonctions prêtes à l'emploi qui peuvent être utilisées avec le modèle de liste de contiguïté pour simplifier la vie.
http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html
la source
J'ai utilisé l'implémentation suivante sur SQL SERVER 2005. Vérifiez ici
la source
Si quelqu'un utilisant MS SQL Server 2008 et supérieur atterrit sur cette question: SQL Server 2008 et supérieur a une nouvelle fonctionnalité «hierarchyId» conçue spécifiquement pour cette tâche.
Plus d'informations sur https://docs.microsoft.com/en-us/sql/relational-databases/hierarchical-data-sql-server
la source