Comment implémenter l'arborescence hautes performances dans SQL Server 2005

Question

Quelle est la meilleure façon de créer la table qui représentera l'arborescence? Je veux implémenter une sélection, une insertion, une mise à jour et une suppression qui fonctionnera bien avec les big data. Le select par exemple devra supporter "Expand ALL" - obtenir tous les enfants (et leurs enfants) pour un nœud donné.

Answer 1

Utilisez CTE 's.

Compte tenu de la structure de la table arborescente:

id parent name 
1 0  Electronics 
2 1  TV 
3 1  Hi-Fi 
4 2  LCD 
5 2  Plasma 
6 3  Amplifiers 
7 3  Speakers 

, cette requête retourne id, parent et le niveau de profondeur, ordonné comme un arbre:

WITH v (id, parent, level) AS 
     (
     SELECT id, parent, 1 
     FROM table 
     WHERE parent = 0 
     UNION ALL 
     SELECT id, parent, v.level + 1 
     FROM v 
     JOIN table t 
     ON  t.parent = v.id 
     ) 
SELECT * 
FROM v 

id parent name 
1 0  Electronics 
2 1  TV 
4 2   LCD 
5 2   Plasma 
3 1  Hi-Fi 
6 3   Amplifiers 
7 3   Speakers 

Remplacer parent = 0 avec parent = @parent pour obtenir seulement une branche d'un arbre.

Pourvu qu'il existe un index sur table (parent), cette requête fonctionnera efficacement sur une très grande table, car elle utilisera récursivement INDEX LOOKUP pour trouver tous les chilrden pour chaque parent.

Pour mettre à jour une branche, numéro:

WITH v (id, parent, level) AS 
     (
     SELECT id, parent, 1 
     FROM table 
     WHERE parent = 0 
     UNION ALL 
     SELECT id, parent, v.level + 1 
     FROM v 
     JOIN table t 
     ON  t.parent = v.id 
     ) 
UPDATE table t 
SET  column = newvalue 
WHERE t.id IN 
     (
     SELECT id 
     FROM v 
     ) 

où @parent est la racine de la branche.

Answer 2

Consultez la section Joe Celko's book on trees and hierarchies pour connaître les différentes manières de résoudre le problème de hiérarchie. Le modèle que vous choisissez dépendra de la façon dont vous pondérez les recherches par rapport aux mises à jour par rapport à la complexité. Vous pouvez effectuer les recherches assez rapidement (en particulier pour obtenir tous les enfants dans un nœud) en utilisant le modèle de liste d'adjacence, mais les mises à jour de l'arborescence sont plus lentes.

Answer 3

Vous devez d'abord vous poser ces questions: 1) Quel est le rapport entre les modifications et les lectures? (= arbre essentiellement statique ou en constante évolution?) 2) Quelle est la profondeur et la grosseur de l'arbre?

Les ensembles imbriqués sont parfaits pour les arbres essentiellement statiques où vous avez besoin d'opérations sur des branches entières. Il gère les arbres profonds sans problèmes.

Le chemin matérialisé fonctionne bien pour les arbres dynamiques (changeants) avec une profondeur contrainte/prévisible.

Les CTE récursifs sont idéaux pour les très petits arbres, mais les opérations de branchement ("avoir tous les enfants dans cette branche ..") deviennent très coûteuses avec un arbre profond/grand.

Answer 4

Si vous avez beaucoup de mises à jour et sélectionne, la meilleure option semble être le chemin Enumeration modèle, qui est brièvement décrit ici:

http://www.sqlteam.com/article/more-trees-hierarchies-in-sql

Answer 5

Je suis surpris que personne n'a mentionné d'aller avec un Closure Table . Très efficace pour les lectures et assez simple à écrire.