Utilisation des types de données hierarchyid (moteur de base de données)
Le type de données hierarchyid est fourni par le système. Le type de données hierarchyid permet de créer des tables avec une structure hiérarchique ou de référencer la structure hiérarchique de données à un autre emplacement. Utilisez des fonctions hierarchyid pour interroger des données hiérarchiques et effectuer un travail sur celles-ci en utilisant Transact-SQL.
Les données hiérarchiques sont définies comme un jeu d'éléments de données liés entre eux par des relations hiérarchiques. Les relations hiérarchiques sont celles dans lesquelles un élément de données est le parent d'un autre élément. Les données hiérarchiques sont très répandues dans les bases de données. En voici quelques exemples :
Structure d'organisation
Système de fichiers
Ensemble de tâches dans un projet
Taxonomie de termes langagiers
Graphique de liens entre pages Web
Le type hierarchyid, nouveau dans SQL Server 2008, simplifie le stockage et l'interrogation des données hiérarchiques. hierarchyid est optimisé pour la représentation des arborescences, qui sont le type de données hiérarchiques le plus courant.
Propriétés principales de hierarchyid
Une valeur du type de données hierarchyid représente une position dans une hiérarchie d'arborescence. Les valeurs de hierarchyid ont les propriétés suivantes :
Extrêmement compact
Le nombre moyen de bits requis pour représenter un nœud dans une arborescence avec n nœuds dépend de la sortance moyenne (nombre moyen d'enfants d'un nœud). Pour les petites sortances (de 0 à 7), la taille est d'environ 6*logAn bits, où A est la sortance moyenne. Un nœud dans une hiérarchie d'organisation de 100 000 personnes avec une sortance moyenne de 6 niveaux prend approximativement 38 bits. Ce chiffre est arrondi à 40 bits, ou 5 octets, pour le stockage.
La comparaison est effectuée dans l'ordre à profondeur prioritaire
Étant donné deux valeurs hierarchyida et b, a<b signifie que a se situe avant b dans un parcours à profondeur prioritaire de l'arborescence. Les index sur les types de données hierarchyid sont dans l'ordre à profondeur prioritaire, et les nœuds proches les uns des autres dans un parcours à profondeur prioritaire sont stockés les uns à côté des autres. Par exemple, les enfants d'un enregistrement sont stockés à côté de cet enregistrement.
Prise en charge des insertions et des suppressions arbitraires
En utilisant la méthode GetDescendant, il est toujours possible de générer un frère à droite d'un nœud donné, à gauche d'un nœud donné ou entre deux frères donnés. La propriété de comparaison est maintenue lorsqu'un nombre arbitraire de nœuds est inséré ou supprimé dans la hiérarchie. La plupart des insertions et suppressions préservent la propriété de compacité. Toutefois, les insertions entre deux nœuds produiront des valeurs hierarchyid ayant une représentation légèrement moins compacte.
Limites de hierarchyid
Les limites du type de données hierarchyid sont les suivantes :
Une colonne de type hierarchyid ne représente pas automatiquement une arborescence. Il appartient à l'application de générer et d'affecter des valeurs hierarchyid de sorte que la relation souhaitée entre les lignes soit reflétée dans les valeurs. Certaines applications peuvent même ne pas souhaiter avoir une colonne de type hierarchyid pour représenter une arborescence. Il se peut que les valeurs soient des références à l'emplacement d'une hiérarchie définie dans une autre table.
Il appartient à l'application de gérer la concurrence en générant et en affectant des valeurs hierarchyid Rien ne garantit que les valeurs hierarchyid d'une colonne sont uniques, à moins que l'application utilise une contrainte de clé unique ou applique elle-même l'unicité selon sa propre logique.
Les relations hiérarchiques représentées par les valeurs hierarchyid ne sont pas appliquées de la même manière qu'une relation de clé étrangère. Dans une relation hiérarchique, il est possible et parfois nécessaire que A ait un enfant B, puis que A soit supprimé, laissant B avec une relation à un enregistrement inexistant. Si ce comportement n'est pas acceptable, l'application doit rechercher des descendants avant de supprimer des parents.
Stratégies d'indexation
Il existe deux stratégies d'indexation des données hiérarchiques :
À profondeur prioritaire
Dans un index à profondeur prioritaire, les lignes d'une sous-arborescence sont stockées à proximité les unes des autres. Par exemple, tous les employés ayant un supérieur sont stockés à proximité de l'enregistrement de celui-ci.
.gif "Les nœuds sont stockés ensemble.")
À largeur prioritaire
Un index à largeur prioritaire stocke les lignes en regroupant les niveaux de la hiérarchie. Par exemple, les enregistrements des employés ayant le même supérieur direct sont stockés à proximité les uns des autres.
.gif "Tous les niveaux hiérarchiques sont stockés ensemble.")
Exemples
La méthode GetLevel() peut être utilisée pour créer un classement à largeur prioritaire. Dans l'exemple suivant, des index à largeur prioritaire et des index à profondeur prioritaire sont créés :
USE AdventureWorks ;
GO
CREATE TABLE Organization
(
EmployeeID hierarchyid,
OrgLevel as EmployeeID.GetLevel(),
EmployeeName nvarchar(50) NOT NULL
) ;
GO
Dans un index à profondeur prioritaire, tous les nœuds dans la sous-arborescence d'un nœud sont colocalisés. Les index à profondeur prioritaire sont par conséquent efficaces pour répondre aux requêtes sur les sous-arborescences, comme « Rechercher tous les fichiers dans ce dossier et ses sous-dossiers ».
CREATE CLUSTERED INDEX Org_Breadth_First
ON Organization(OrgLevel,EmployeeID) ;
GO
CREATE UNIQUE INDEX Org_Depth_First
ON Organization(EmployeeID) ;
GO
Dans un index à largeur prioritaire, tous les enfants directs d'un nœud sont colocalisés. Les index à largeur prioritaire sont par conséquent efficaces pour répondre aux requêtes sur les enfants immédiats, telle que « Rechercher tous les employés dont ce responsable est le supérieur direct ».
Le choix entre profondeur prioritaire, largeur prioritaire ou les deux, et la sélection de l'un d'eux comme clé de clustering (si nécessaire) dépend de l'importance relative des types de requêtes ci-dessus et de l'importance relative de SELECT par rapport aux opérations DML. Pour un exemple détaillé de stratégies d'indexation, consultez Didacticiel : utilisation du type de données hierarchyid.
Quand utiliser des alternatives à hierarchyid
Les deux alternatives à hierarchyid pour représenter des données hiérarchiques sont les suivantes :
Parent/enfant
XML
hierarchyid est généralement supérieur à ces alternatives. Toutefois, il existe certaines situations spécifiques, détaillées ci-dessous, pour lesquelles ces alternatives peuvent s'avérer supérieures.
Parent/enfant
Lors de l'utilisation de l'approche de parent/enfant, chaque ligne contient une référence au parent. La table suivante définit une table classique qui est utilisée pour contenir les lignes parent et enfant dans une relation parent/enfant :
USE AdventureWorks ;
GO
CREATE TABLE ParentChildOrg
(
EmployeeID int PRIMARY KEY,
ManagerId int REFERENCES ParentChildOrg(EmployeeID),
EmployeeName nvarchar(50)
) ;
GO
Comparaison de parent/enfant et hierarchyid pour les opérations courantes
Les requêtes de sous-arborescence sont beaucoup plus rapides avec hierarchyid
Les requêtes de descendants directs sont légèrement plus lentes avec hierarchyid
Le déplacement de nœuds non terminaux est beaucoup plus lent avec hierarchyid. L'insertion de nœuds non terminaux et l'insertion ou le déplacement de nœuds terminaux présentent la même complexité avec hierarchyid.
Il se peut que la relation parent/enfant soit supérieure si les conditions suivantes sont réunies :
La taille de la clé est très critique. Pour le même nombre de nœuds, une valeur hierarchyid est égale ou supérieure à une valeur de famille d'entiers (smallint, int, bigint). Cela ne constitue une raison d'utiliser la relation parent/enfant que dans de rares cas, car la localité d'E/S et la complexité de l'UC de hierarchyid sont meilleures que celles des expressions de table communes requises lorsque vous utilisez une structure parent/enfant.
Les requêtes portent rarement sur plusieurs sections de la hiérarchie. En d'autres termes, les requêtes portent habituellement sur un seul point de la hiérarchie. Dans ces cas, la co-location n'est pas importante. Par exemple, parent/enfant est supérieur si la table d'organisation est utilisée uniquement pour l'exécution des salaires d'employés individuels.
Les sous-arborescences qui ne sont pas au niveau du nœud terminal sont fréquemment déplacées et les performances sont importantes. Dans une représentation parent/enfant, la modification de l'emplacement d'une ligne dans une hiérarchie affecte une seule ligne. La modification de l'emplacement d'une ligne dans une utilisation de hierarchyid affecte n lignes, où n est le nombre de nœuds dans la sous-arborescence déplacée.
Si les sous-arborescences qui ne sont pas au niveau du nœud terminal sont fréquemment déplacées et que les performances sont importantes, mais que la plupart des déplacements se font à un niveau bien défini de la hiérarchie, envisagez le fractionnement des niveaux supérieurs et inférieurs en deux hiérarchies. Tous les déplacements se font ainsi dans les niveaux du nœud terminal de la hiérarchie supérieure. Prenons par exemple une hiérarchie de sites Web hébergés par un service. Les sites contiennent de nombreuses pages organisées de façon hiérarchique. Les sites hébergés peuvent être déplacés vers d'autres emplacements dans la hiérarchie de site, mais les pages subordonnées sont rarement réorganisées. Cela peut être représenté de la manière suivante :
CREATE TABLE HostedSites ( SiteId hierarchyid, PageId hierarchyid ) ; GO
XML
Un document XML est une arborescence. Par conséquent, une instance de type de données XML unique peut représenter la totalité d'une hiérarchie. Dans SQL Server, lorsqu'un index XML est créé, les valeurs hierarchyid sont utilisées en interne pour représenter la position dans la hiérarchie.
Il peut être préférable d'utiliser le type de données XML lorsque les conditions suivantes sont réunies :
La hiérarchie est toujours stockée et extraite dans sa totalité.
Les données sont consommées au format XML par l'application.
Les recherches de prédicat sont extrêmement limitées et non critiques pour les performances.
Par exemple, si une application effectue le suivi de plusieurs organisations, stocke et extrait toujours la totalité de la hiérarchie d'organisation et que ses requêtes ne portent pas sur une organisation unique, une table se présentant au format suivant peut être appropriée :
CREATE TABLE XMLOrg
(
Orgid int,
Orgdata xml
) ;
GO
Migration de parent/enfant vers hierarchyid
La plupart des arborescences sont aujourd'hui représentées à l'aide de parent/enfant. La méthode la plus simple pour effectuer une migration d'une structure parent/enfant vers une table à l'aide de hierarchyid est d'utiliser une colonne ou une table temporaire pour conserver une trace du nombre de nœuds à chaque niveau de la hiérarchie. Pour voir un exemple de migration de table parent/enfant, consultez la leçon 1 de Didacticiel : utilisation du type de données hierarchyid.
Transformations de requêtes pour hierarchyid
Pour augmenter les performances d'interrogation des hiérarchies, SQL Server effectue automatiquement trois transformations de requêtes impliquant hierarchyid Le résultat de ces transformations peut être consulté dans la sortie du plan d'exécution pour les requêtes transformées.
IsDescendantOf est transformé en recherche de plage
Étant donné E comme colonne ou comme variable, E.IsDescendantOf(c) est transformé en recherche de plage. Cela réduit considérablement le coût de la recherche de descendants. S'il existe un index à profondeur prioritaire sur E, cette transformation est bénéfique car tous les descendants de E sont colocalisés. Par exemple, l'extrait de code EmployeeId.IsDescendantOf(@value) est exécuté comme EmployeeId >= @Value AND EmployeeId <= @Value.DescendantLimit(). DescendantLimit est une méthode interne qui détermine la moindre limite supérieure de tous les descendants possibles d'un nœud. Notez que @value ne doit pas nécessairement être un paramètre. Il peut s'agir d'une colonne, par exemple d'une condition de jointure.
GetAncestor est transformé en analyse d'étendue et en prédicat résiduel
GetAncestor(n) donne le nième ancêtre d'un nœud. Cela est utile lorsque la relation précise (parent, enfant, grand-parent, etc.) entre deux nœuds est requise, à l'inverse de la relation IsDescendantOf plus générale.
Par exemple, exécutez la requête suivante pour rechercher tous les employés dont le responsable direct est @value :
SELECT * FROM Employees WHERE EmployeeId.GetAncestor(1) = @value
Cela devient une analyse de plage pour les descendants de @value, avec le prédicat d'origine comme élément résiduel. Le code est transformé comme suit :
SELECT * FROM Employees
WHERE
EmployeeId >= @Value AND EmployeeId <= @value.DescendantLimit()
AND EmployeeId.GetAncestor(1) = @value
Cela a pour effet de limiter l'analyse à la sous-arborescence de @value.
GetAncestor est transformé en une recherche d'index à l'aide de l'index à largeur prioritaire
Dans la requête ci-dessus, si @value se situe dans les niveaux supérieurs de l'arborescence, l'optimisation ne réduit pas significativement le nombre de lignes analysées. Lorsque les questions relatives au nième ancêtre sont courantes, les applications doivent créer un index à largeur prioritaire, comme précédemment décrit.
Lorsqu'il existe un index à largeur prioritaire, la requête ci-dessus est ensuite transformée comme suit :
SELECT * FROM Employees
WHERE
EmployeeId >=@value AND EmployeeId <= @Value.DescendantLimit()
AND @value.GetLevel()+1 = EmployeeId.GetLevel()
La dernière ligne (contenant les méthodes GetLevel) devient une recherche d'index dans l'index à largeur prioritaire. Si EmployeeId est la clé de clustering, alors il s'agit de la deuxième colonne de l'index à largeur prioritaire ; les deux prédicats deviennent une recherche d'index qui spécifie exactement les n rapports directs colocalisés de @value.
Les transformations GetAncestor ne sont pas limitées aux requêtes de parents directs. L'argument pour GetAncestor peut être n'importe quelle variable ou constante.