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.

• À 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.

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 AdventureWorks2008R2 ; 
GO

CREATE TABLE Organization
   (
    BusinessEntityID hierarchyid,
    OrgLevel as BusinessEntityID.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,BusinessEntityID) ;
GO

CREATE UNIQUE INDEX Org_Depth_First 
ON Organization(BusinessEntityID) ;
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 AdventureWorks2008R2 ;
GO

CREATE TABLE ParentChildOrg
   (
    BusinessEntityID int PRIMARY KEY,
    ManagerId int REFERENCES ParentChildOrg(BusinessEntityID),
    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.

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 :

DECLARE @value hierarchyid ;
SELECT * FROM AdventureWorks2008R2.HumanResources.Employee 
WHERE  OrganizationNode.IsDescendantOf(@value) = 1;

Voir aussi

Référence

hierarchyid (Transact-SQL)

Concepts

Utilisation du type de données hierarchyid

Référence de méthodes de type de données hierarchyid

Didacticiel : utilisation du type de données hierarchyid