Structure de la base de données pour la Structure des données des arbres
quelle serait la meilleure façon de mettre en œuvre une structure de données personnalisable (c'est-à-dire une structure arborescente avec un nombre inconnu de niveaux) dans une base de données?
j'ai fait cela une fois avant d'utiliser une table avec une clé étrangère à lui-même.
quelles autres implémentations pourriez-vous voir, et est-ce que cette implémentation a du sens?
6 réponses
vous mentionnez le plus souvent mis en œuvre, qui est la liste de contiguïté: https://blogs.msdn.microsoft.com/mvpawardprogram/2012/06/25/hierarchies-convert-adjacency-list-to-nested-sets
il y a d'autres modèles aussi, y compris chemin matérialisé et ensembles imbriqués: http://communities.bmc.com/communities/docs/DOC-9902
Joe Celko a écrit un livre sur ce sujet, qui est un bon référence D'un point de vue SQL général (il est mentionné dans l'article imbriqué lien ci-dessus).
aussi, 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 principales choses à considérer lors du choix d'un modèle sont:
1) fréquence des changements de structure - à quelle fréquence la structure réelle de l'arbre change-t-elle? Certains modèles permettent de mieux structurer mettre à jour les caractéristiques. Il est toutefois important de séparer les changements de structure des autres changements de données. Par exemple, vous pourriez vouloir modéliser l'organigramme d'une entreprise. Certaines personnes vont modéliser cette liste comme une liste de contiguïté, en utilisant le numéro d'identification de l'employé pour relier un employé à son superviseur. Il s'agit habituellement d'une approche sous-optimale. Une approche qui fonctionne souvent mieux est de modéliser la structure de l'organisation séparément des employés eux-mêmes, et de maintenir l'employé comme un attribut de la structure. De cette façon, lorsqu'un employé quitte l'entreprise, la structure organisationnelle elle-même n'a pas besoin de changements, il suffit de l'association avec l'employé de la gauche.
2) est l'arbre à écrire-lourd ou à lire-lourd - certaines structures fonctionnent très bien lors de la lecture de la structure, mais entraînent des frais généraux supplémentaires lors de l'écriture à la structure.
3) Quels types d'Informations devez - vous obtenir de la structure-certaines structures excellent à fournir certains types de des informations sur la structure. Par exemple, trouver un nœud et tous ses enfants, Trouver un nœud et tous ses parents, trouver le nombre de nœuds enfants répondant à certaines conditions, etc. Vous devez savoir quelle information sera nécessaire à partir de la structure pour déterminer la structure qui répondra le mieux à vos besoins.
regarder la Gestion Hiérarchique des Données dans MySQL . Il traite de deux approches pour stocker et gérer des données hiérarchiques (de type arborescent) dans une base de données relationnelle.
la première approche est le modèle de liste de contiguïté, qui est ce que vous décrivez essentiellement: avoir une clé étrangère qui se réfère à 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'arbre entier.
la deuxième approche discutée dans l'article est le modèle emboîté. Cette approche est beaucoup plus efficace et souple. Consultez l'article pour une explication détaillée et des exemples de requêtes.
si vous devez utiliser la base de données relationnelle pour organiser la structure de données de l'arbre, Postgresql dispose d'un module ltree cool qui fournit le type de données pour représenter les étiquettes de données stockées dans une structure hiérarchique arborescente. Vous pouvez obtenir de l'idée à partir de là.(Pour plus d'informations, voir: http://www.postgresql.org/docs/9.0/static/ltree.html )
dans LDAP commun est utilisé pour organiser les enregistrements dans la structure hiérarchique.
avoir une table avec une clé étrangère à lui-même a du sens pour moi.
vous pouvez alors utiliser une expression de table commune dans SQL ou le connect par déclaration préalable dans Oracle pour construire votre arbre.
fantastique collection de fonctions prêtes à l'emploi qui peuvent être utilisées avec le modèle de liste adjacente pour rendre la vie plus simple.
http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html