SQL optimisé pour les structures d'arbres

Question

Comment voulez-vous obtenir de l'arbre structuré de données à partir d'une base de données avec le meilleur rendement? Par exemple, disons que vous avez un dossier de hiérarchie dans une base de données. Lorsque le dossier de la base de données-ligne a ID, Nom et ParentID colonnes.

Souhaitez-vous utiliser un algorithme spécial pour obtenir toutes les données à la fois, réduisant la quantité de la base de données des appels et des processus dans le code?

Ou utilisez-vous faire de nombreux appels à la base de données et de tri d'obtenir la structure de la base de données directement?

Peut-être il y a différentes réponses basées sur la quantité de x de la base de données de lignes, de hiérarchie, de la profondeur ou quoi?

Edit: j'utilise Microsoft SQL Server, mais des réponses à partir d'autres points de vue sont intéressants aussi.

Answer 1

Cela dépend vraiment de la façon dont vous allez accéder à l'arbre.

Une technique intelligente est de donner à chaque nœud un id de chaîne, où l'id du parent est une sous-chaîne prévisible de l'enfant. Par exemple, le parent pourrait être '01', et les enfants seraient '0100', '0101', '0102', etc. De cette façon, vous pouvez sélectionner un sous-arbre entier à partir de la base de données à la fois avec:

Étant donné que le critère est une sous-chaîne initiale, un index sur la colonne d'ID accélérerait la requête.

Answer 2

De toutes les façons de stocker un arbre dans un SGBDR les plus courantes sont les listes d'adjacence et imbriqués de jeux. Imbriquée jeux sont optimisés pour les lectures et peut récupérer un arbre entier dans une seule requête. Les listes d'adjacence sont optimisés pour l'écrit et peuvent être ajoutés à une requête simple.

La contiguïté des listes de chaque nœud a, colonne fait référence au nœud parent ou l'enfant du nœud (d'autres liens sont possibles). L'aide que vous pouvez construire la hiérarchie basée sur les relations parent-enfant. Malheureusement, sauf si vous limitez votre arbre de profondeur vous ne pouvez pas tirer la chose entière dans une seule requête et de la lecture, il est généralement plus lent que de le mettre à jour.

Avec l'ensemble imbriqué modèle l'inverse est vrai, la lecture est rapide et facile, mais les mises à jour deviennent complexes parce que vous devez maintenir le système de numérotation. L'ensemble imbriqué modèle de code à la fois la filiation et l'ordre de tri par l'énumération de tous les nœuds à l'aide d'une précommande en fonction d'un système de numérotation.

J'ai utilisé l'ensemble imbriqué de modèle et s'il est complexe pour lire l'optimisation d'un grand hiérarchie, il en vaut la peine. Une fois que vous faites quelques exercices dans le dessin de l'arbre et de la numérotation des nœuds, vous devriez obtenir le blocage de celui-ci.

Mes recherches sur cette méthode commencé à cet article: la Gestion Hiérarchique des Données dans MySQL.

Answer 3

examiner le modèle de hiérarchie des ensembles nichés. c'est assez cool et utile.

Answer 4

Celko écrit à ce sujet (2000):

http://www.dbmsmag.com/9603d06.html

http://www.intelligententerprise.com/001020/celko1_1.jhtml;jsessionid=3DFR02341QLDEQSNDLRSKHSCJUNN2JVN?_requestid=32818

---

et d'autres personnes ont demandé:

http://stackoverflow.com/questions/117512/joining-other-tables-in-oracle-tree-queries

http://stackoverflow.com/questions/91360/how-to-calculate-the-sum-of-values-in-a-tree-using-sql

http://stackoverflow.com/questions/144344/how-to-store-directory-hierarchy-tree-structure-in-the-database

http://stackoverflow.com/questions/221194/performance-of-recursive-stored-procedures-in-mysql-to-get-hierarchical-data

http://stackoverflow.com/questions/192220/what-is-the-most-efficientelegant-way-to-parse-a-flat-table-into-a-tree

---

enfin, vous pouvez regarder les rails "acts_as_tree" (lire-lourds) et "acts_as_nested_set" (écriture lourde) des plugins. Je n'ai pas de bonne liaison et de les comparer.