Quelles sont les Options pour le Stockage de Données Hiérarchiques dans une Base de données Relationnelle?

Question

Bon Aperçus

De manière générale, vous êtes prise d'une décision rapide entre les temps de lecture (par exemple ensemble imbriqué) ou rapide le temps d'écriture (liste d'adjacence). Habituellement, vous vous retrouvez avec une combinaison des options ci-dessous qui correspondent le mieux à vos besoins. Le texte qui suit présente certains à la lecture approfondie:

• Un Imbriqués Intervalles vs la Contiguïté de la Liste de comparaison: le meilleur de la comparaison de la Liste d'Adjacence, Chemin Matérialisé, Ensemble Imbriqué et Imbriquées Intervalle, j'ai trouvé.
• Les modèles de données hiérarchiques: les lames avec de bonnes explications de compromis et exemple d'utilisation
• Représentant des hiérarchies dans MySQL: très bon aperçu de l'Ensemble Imbriqué en particulier
• Des données hiérarchiques dans les Sgbdr: plus complet et le mieux organisé une série de liens que j'ai vu, mais pas beaucoup dans la voie de l'explication

Options

Ceux que je suis au courant et caractéristiques générales:

1. La Contiguïté De La Liste:
   • Colonnes: ID, ParentID
   • Facile à mettre en œuvre.
   • Pas cher nœud se déplace, des insertions et des suppressions.
   • Cher pour trouver niveau (peut stocker qu'une colonne calculée), de l'ascendance et la descendance (Table de Bridge combiné avec le niveau de la colonne peut résoudre), chemin (de la Lignée de la Colonne peut résoudre).
   • L'utilisation d'Expressions de Table Communes dans ces bases de données qui les aident à traverser.
2. Ensemble imbriqué (un.k.une modification de la Précommande Arbre Transversal)
   • Popularisé par Joe Celko dans de nombreux articles et son livre des Arbres et des Hiérarchies dans SQL pour les Smarties
   • Colonnes: À Gauche, À Droite
   • Pas cher niveau, de l'ascendance, de descendance
   • Par rapport à la Liste d'Adjacence, les coups, les insertions, les suppressions plus cher.
   • Nécessite un ordre de tri (par exemple créé). Donc un tri de tous les descendants dans un ordre différent nécessite plus de travail.
3. Imbriqués Les Intervalles De
   • Combinaison de Imbriquée Sets et Chemin Matérialisé où de gauche/droite des colonnes sont des nombres à virgule des décimales au lieu de nombres entiers et de coder les informations de chemin d'accès. Dans le développement ultérieur de cette idée imbriquée intervalles a donné lieu à la matrice de codage.
4. Table de Bridge (un.k.un. Fermeture de la Table: quelques bonnes idées sur la façon d'utiliser des déclencheurs pour le maintien de cette approche)
   • Colonnes: ancêtre, descendant
   • Se démarque de tableau qu'il décrit.
   • Peut inclure des nœuds dans plus d'une hiérarchie.
   • Bon marché de l'ascendance et de la descendance (mais pas dans l'ordre)
   • Pour compléter la connaissance de la hiérarchie doit être combinée avec une autre option.
5. Table À Plat
   • Une modification de la Liste d'Adjacence, qui ajoute un Niveau et le Rang (par exemple, la commande) colonne pour chaque enregistrement.
   • Cher déplacer et de supprimer des
   • Bon marché de l'ascendance et de descendance
   • Bon Usage: fils de discussion - forum / blog de commentaires
6. La lignée de la Colonne (un.k.un. Chemin Matérialisé, Chemin De L'Énumération)
   • Colonne: la lignée (par exemple, /parent/enfant/petit enfant/etc...)
   • De limite à la profondeur de la hiérarchie peut être.
   • Les Descendants à bas prix (par exemple, LEFT(lineage, #) = '/enumerated/path')
   • Ancestry délicate (base de données des requêtes spécifiques)
7. Plusieurs colonnes de lignage
   • Colonnes: une pour chaque lignée niveau, se réfère à tous les parents jusqu'à la racine, les niveaux plus bas que les éléments de niveau sont mis à NULL
   • De limite à la profondeur de la hiérarchie peut être
   • Pas cher ascendants, descendants, niveau
   • Bon marché insérer, supprimer, déplacer des feuilles
   • Cher, insérer, supprimer, déplacer des nœuds internes

Base De Données Des Notes Spécifiques

MySQL

• Utiliser des variables de session pour la Liste d'Adjacence

Oracle

• L'utilisation de CONNECTER PAR de parcourir les Listes d'Adjacence

PostgreSQL

• ltree type de données pour le Chemin Matérialisé

SQL Server

• Résumé général
• 2008 offre HierarchyId type de données apparaît pour vous aider avec la Lignée de la Colonne d'approche et d'étendre la profondeur qui peut être représenté.

Answer 1

Mon préféré réponse est que ce que la première phrase de ce fil suggéré. Utiliser une Liste d'Adjacence pour maintenir la hiérarchie et de l'utilisation Imbriquée Définit à la requête de la hiérarchie.

Le problème jusqu'à maintenant a été que la coversion méthode à partir d'un Adjacecy Liste Imbriquée Ensembles a été horriblement lent, car la plupart des gens utilisent l'extrême RBAR méthode connue sous le nom de "Pousser la Pile des" à faire la conversion et a été considéré comme un moyen de coûteux d'atteindre le Nirvana de la simplicité de maintenance de la Liste d'Adjacence et la performance impressionnante de Imbriquée Ensembles. En conséquence, la plupart des gens finissent par avoir à trancher pour l'un ou l'autre, surtout si il ya plus de, disons, un moche de 100 000 nœuds. L'utilisation de la commande de la pile méthode peut prendre une journée entière pour faire la conversion sur ce MLM ils considèrent comme un petit million de nœud de hiérarchie.

J'ai pensé donner Celko un peu de la concurrence et à venir avec une méthode pour convertir une Liste d'Adjacence Imbriquées jeux à des vitesses qui semblent tout simplement impossible. Voici la performance de la pile push méthode sur mon i5 ordinateur portable.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

Et voici la durée de la nouvelle méthode (avec la poussée de la pile de la méthode dans la parenthèse).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

Oui, c'est correct. 1 million de nœuds convertis en moins d'une minute et 100 000 nœuds en moins de 4 secondes.

Vous pouvez lire au sujet de la nouvelle méthode et d'obtenir une copie du code à l'adresse suivante. http://www.sqlservercentral.com/articles/Hierarchy/94040/

J'ai également développé un "pré-agrégées" hiérarchie à l'aide de méthodes similaires. MLM croyants et les gens qui font des listes de matériaux seront particulièrement intéressés par le présent article. http://www.sqlservercentral.com/articles/T-SQL/94570/

Si vous ne s'arrêter pour jeter un oeil à l'article, sauter dans le "Join the discussion" et laissez-moi savoir ce que vous en pensez.

Answer 2

C'est le genre de question qui est toujours intéressant, même après tous les big 3 vendeurs mis en œuvre Récursive WITH de la clause. Je suggère que les différents lecteurs seraient heureux avec des réponses différentes.

1. Liste complète des références par Troels Arvin.
2. Pour le manque de concurrence, dans l'introduction, un ouvrage de Joe Celko "des Arbres et des Hiérarchies dans SQL pour les Smarties" peut en effet être considéré comme un des classiques.
3. Examen de diverses arbre encodages avec l'accent de imbriquée intervalles.

Answer 3

C'est un très répondre en partie à votre question, mais j'espère toujours utile.

Microsoft SQL Server 2008 met en œuvre deux caractéristiques qui sont extrêmement utiles pour la gestion des données hiérarchiques:

• le HierarchyId type de données.
• les expressions de table communes, à l'aide de la avec mot-clé.

Jetez un oeil à cet article pour les mises en chantier. Voir aussi ma propre question ici.

Answer 4

Certains articles de mon blog sur le sujet:

• Liste d'adjacence vs imbriquée ensembles: MySQL
• Liste d'adjacence vs imbriquée ensembles: PostgreSQL
• Liste d'adjacence vs imbriquée ensembles: Oracle

• Liste d'adjacence vs imbriquée ensembles: SQL Server

• Des requêtes hiérarchiques dans MySQL (interrogation de listes d'adjacence en MySQL)

Answer 5

Joe Celko écrit le livre sur SQL Arbres & Hiearichies

C'est la première édition. Regardez la deuxième édition de Bob commentaire.