Verwenden von hierarchyid-Datentypen (Datenbankmodul)

Der hierarchyid-Datentyp wird vom System bereitgestellt. Mit dem Datentyp hierarchyid können Sie Tabellen mit einer hierarchischen Struktur erstellen oder auf hierarchisch geordnete Daten an einem anderen Speicherort verweisen. Verwenden Sie hierarchyid-Funktionen, um hierarchische Daten mit Transact-SQL abzufragen und zu bearbeiten.

Hierarchische Daten sind definiert als Satz von Datenelementen, die durch hierarchische Beziehungen miteinander verbunden sind. Hierarchische Beziehungen liegen vor, wenn ein Datenelement einem anderen Element übergeordnet ist. Hierarchische Daten kommen in Datenbanken häufig vor. Einige Beispiele dafür sind:

• Eine Organisationsstruktur

• Ein Dateisystem

• Eine Gruppe von Aufgaben in einem Projekt.

• Ein Taxonomie sprachlicher Termini

• Ein Diagramm der Links zwischen Webseiten

Der neu in SQL Server 2008 eingeführte Typ hierarchyid vereinfacht die Speicherung und Abfrage hierarchischer Daten. Der Typ hierarchyid wurde für die Darstellung von Baumstrukturen, dem verbreitetsten Typ hierarchischer Daten, optimiert.

Haupteigenschaften von hierarchyid

Ein Wert des hierarchyid-Datentyps stellt eine Position in einer Strukturhierarchie dar. Werte des Typs hierarchyid verfügen über die folgenden Eigenschaften:

• Äußerst komprimiert

  Die durchschnittliche Zahl der Bits, die erforderlich sind, um einen Knoten in einer Baumstruktur mit n Knoten darzustellen, hängt von der durchschnittlichen Anzahl der Verzweigungen (der durchschnittlichen Anzahl untergeordneter Knoten) eines Knotens ab. Bei wenigen Verzweigungen (0-7) entspricht diese Zahl etwa 6*logAn Bit, wobei A die durchschnittliche Anzahl der Verzweigungen angibt. Ein Knoten in einer 100.000 Personen umfassenden Organisationshierarchie mit durchschnittlich 6 Verzweigungen benötigt etwa 38 Bit. Dieser Wert wird bei der Speicherung auf 40 Bit oder 5 Byte aufgerundet.

• Vergleiche erfolgen in Tiefensuchreihenfolge

  Bei den beiden hierarchyid-Werten a und b, bedeutet a<b, dass beim Durchlaufen der Baumstruktur in der Tiefensuchreihenfolge a vor b kommt. Indizes für hierarchyid-Datentypen verwenden die Tiefensuchreihenfolge, und einander benachbarte Knoten werden bei der Tiefensuchreihenfolge nahe beieinander gespeichert. Ein einem Datensatz untergeordneter Datensatz wird zum Beispiel angrenzend an diesen Datensatz gespeichert.

• Unterstützung willkürlicher Einfüge- und Löschoperationen

  Mithilfe der GetDescendant-Methode ist es immer möglich, rechts oder links von einem gegebenen Knoten einen gleichgeordneten Knoten zu erstellen oder ihn auch zwischen zwei Knoten einzufügen. Die Vergleichseigenschaft bleibt auch dann gewahrt, wenn eine beliebige Anzahl von Knoten in die Hierarchie eingefügt oder aus ihr gelöscht wird. Die meisten Einfüge- und Löschoperationen behalten die Kompaktheitseigenschaft bei. Einfügungen zwischen zwei Knoten erzeugen jedoch hierarchyid-Werte in einer etwas weniger kompakten Darstellung.

Einschränkungen von hierarchyid

Für den hierarchyid-Datentyp gelten folgende Einschränkungen:

• Eine Spalte des Typs hierarchyid stellt nicht automatisch eine Baumstruktur dar. Es ist Aufgabe der Anwendung, hierarchyid-Werte so zu erstellen und zuzuweisen, dass die gewünschte Beziehung anhand der Werte zu erkennen ist. Einige Anwendungen möchten nicht einmal, dass eine Spalte des Typs hierarchyid eine Baumstruktur repräsentiert. Vielleicht sind die Werte Verweise auf Positionen in einer Hierarchie, die in einer anderen Tabelle definiert ist.

• Es ist Aufgabe der Anwendung, die Parallelität zu verwalten, indem sie geeignete hierarchyid-Werte generiert und zuweist. Es gibt keine Garantie dafür, dass die hierarchyid-Werte einer Spalte eindeutig sind, sofern die Anwendung keine Einschränkung für einen eindeutigen Schlüssel verwendet oder selbst dafür sorgt, dass eindeutige Werte erzeugt werden.

• Hierarchische, durch hierarchyid-Werte dargestellte Beziehungen werden nicht wie Fremdschlüsselbeziehungen durchgesetzt. Es ist möglich und manchmal auch angemessen, eine hierarchische Beziehung herzustellen, in der das Element B dem Element A untergeordnet ist, um dann A zu löschen, wodurch B mit einer Beziehung zu einem nicht mehr vorhandenen Datensatz verbleibt. Wenn dieses Verhalten unannehmbar ist, muss die Anwendung vor dem Löschen von Elementen prüfen, ob untergeordnete Elemente vorhanden sind.

Indizierungsstrategien

Für die Indizierung hierarchischer Daten gibt es zwei Strategien:

• Tiefensuche

  Bei einem Tiefensuchindex werden Zeilen in einer Teilstruktur nahe beieinander gespeichert. Zum Beispiel werden alle Mitarbeiter, die einem bestimmten Manager berichten, in der Nähe des Datensatzes dieses Managers gespeichert.

• Breitensuche

  Bei einem Breitensuchindex werden die Zeilen jeder Ebene der Hierarchie zusammen gespeichert. Zum Beispiel werden die Datensätze aller Mitarbeiter, die direkt einem bestimmten Manager berichten, nahe beieinander gespeichert.

Beispiele

Die GetLevel()-Methode kann verwendet werden, um eine Breitensuchreihenfolge zu erstellen. Im folgenden Beispiel werden sowohl Breitensuch- als auch Tiefensuchindizes erstellt:

USE AdventureWorks ; 
GO

CREATE TABLE Organization
   (
    EmployeeID hierarchyid,
    OrgLevel as EmployeeID.GetLevel(), 
    EmployeeName nvarchar(50) NOT NULL
   ) ;
GO

In einem Tiefensuchindex sind alle Knoten in der Teilstruktur eines Knotens zusammen angeordnet. Daher sind Tiefensuchindizes besonders effizient bei der Abfrage von Teilstrukturen, etwa bei Abfragen des Typs "Ermittle alle Dateien in diesem Ordner und seinen Unterordnern".

CREATE CLUSTERED INDEX Org_Breadth_First 
ON Organization(OrgLevel,EmployeeID) ;
GO

CREATE UNIQUE INDEX Org_Depth_First 
ON Organization(EmployeeID) ;
GO

In einem Breitensuchindex sind alle einem Knoten untergeordneten Knoten zusammen angeordnet. Daher sind Breitensuchindizes besonders effizient bei der Abfrage von unmittelbar untergeordneten Elementen, etwa bei Abfragen des Typs "Ermittle alle Angestellten, die direkt diesem Manager berichten".

Ob Sie einen Tiefen- oder Breitensuchindex verwenden und welchen Sie (wenn überhaupt) als Gruppierungsschlüssel definieren, hängt von der relativen Wichtigkeit der oben genanten Abfragetypen ab sowie von der relativen Wichtigkeit von SELECT- gegenüber DML-Operationen. Ein ausführliches Beispiel zu Indizierungsstrategien finden Sie unter Lernprogramm: Verwenden des hierarchyid-Datentyps.

Wann Alternativen zu hierarchyid zu verwenden sind

Zur Darstellung hierarchischer Daten gibt es zwei Alternativen zu hierarchyid. Diese sind:

• Parent-Child

• XML

hierarchyid ist diesen Alternativen im Allgemeinen überlegen. Jedoch gibt es bestimmte, unten aufgelistete Situationen, in denen diese Alternativen wahrscheinlich überlegen sind.

Parent-Child

Bei dem Parent-Child-Ansatz enthält jede Zeile einen Verweis auf das übergeordnete Element. Im folgenden Beispiel wird eine typische Tabelle definiert, welche die über- und untergeordneten Zeilen einer Parent-Child-Beziehung enthält.

USE AdventureWorks ;
GO

CREATE TABLE ParentChildOrg
   (
    EmployeeID int PRIMARY KEY,
    ManagerId int REFERENCES ParentChildOrg(EmployeeID),
    EmployeeName nvarchar(50) 
   ) ;
GO

Vergleich von Parent-Child mit hierarchyid bei allgemeinen Vorgängen

• Teilstrukturabfragen sind mit hierarchyid bedeutend schneller.

• Abfragen für direkt untergeordnete Elemente sind bei hierarchyid etwas langsamer.

• Das Verschieben innerer Knoten erfolgt bei hierarchyid langsamer. Das Einfügen innerer Knoten und das Einfügen oder Verschieben von Blattknoten weisen bei hierarchyid die gleiche Komplexität auf.

Parent-Child könnte überlegen sein, wenn die folgenden Bedingungen vorliegen:

• Die Größe des Schlüssels ist sehr wichtig. Bei gleicher Anzahl von Knoten ist ein hierarchyid-Wert gleich groß oder größer als ein ganzzahliger Wert (smallint, int, bigint). Das ist allerdings nur in seltenen Fällen ein Grund, Parent-Child zu verwenden, denn hierarchyid ist bezüglich E/A- und CPU-Auslastung weitaus effizienter als die allgemeinen Tabellenausdrücke, die bei Verwendung einer Parent-Child-Struktur erforderlich sind.

• Abfragen erstrecken sich selten über Abschnitte der Hierarchie. Eine Abfrage bezieht sich mit anderen Worten in der Regel auf einen bestimmten Punkt in der Hierarchie. In diesen Fällen ist die benachbarte Speicherung der Elemente nicht wichtig. Eine Parent-Child-Struktur ist beispielsweise dann überlegen, wenn die Organisationstabelle nur für die Gehaltsdaten einzelner Angestellter verwendet wird.

• Innere Knotenteilstrukturen verschieben sich häufig, und dabei ist die Leistung sehr wichtig. Wird in einer Parent-Child-Struktur die Position einer Zeile in der Hierarchie geändert, ist davon nur eine einzelne Zeile betroffen. Die Änderung der Position einer Zeile in einer hierarchyid-Struktur betrifft n Zeilen, wobei n die Zahl der Knoten angibt, die in der Teilstruktur verschoben werden.

  Wenn sich innere Knotenteilstrukturen häufig verschieben und die Leistung sehr wichtig ist, jedoch die meisten Verschiebeoperationen auf einer wohldefinierten Ebene der Hierarchie stattfinden, sollten Sie erwägen, die höheren und die unteren Ebenen in zwei Hierarchien aufzuteilen. Dadurch beschränken sich alle Verschiebungen auf Blattebenen der höheren Hierarchie. Betrachten Sie beispielsweise eine Hierarchie der von einem Dienst gehosteten Websites. Websites enthalten viele auf hierarchische Weise angeordnete Seiten. Gehostete Sites können an einen anderen Ort innerhalb der Site-Hierarchie verschoben werden, jedoch werden die untergeordneten Seiten nur selten neu angeordnet. Dies könnte wie folgt dargestellt werden:

  CREATE TABLE HostedSites 
     (
      SiteId hierarchyid, PageId hierarchyid
     ) ;
  GO
  

XML

Ein XML-Dokument ist eine Baumstruktur, daher kann eine einzige Instanz eines XML-Datentyps eine vollständige Hierarchie repräsentieren. Wird in SQL Server ein XML-Index erstellt, werden intern hierarchyid-Werte verwendet, die die Position in der Hierarchie angeben. 

Die Verwendung des XML-Datentyps kann überlegen sein, wenn alle folgenden Punkte zutreffen:

• Es wird immer die vollständige Hierarchie gespeichert und abgerufen.

• Die Daten werden von der Anwendung im XML-Format verarbeitet.

• Prädikatssuchen werden äußerst selten verwendet und die Leistung ist nicht wichtig.

Wenn eine Anwendung zum Beispiel mehrere Organisationen verfolgt, immer die gesamte Organisationshierarchie speichert und abruft sowie keine einzelne Organisation abfragt, dann könnte eine Tabelle der folgenden Form sinnvoll sein:

CREATE TABLE XMLOrg 
    (
    Orgid int,
    Orgdata xml
    ) ;
GO

Migrieren von Parent-Child zu hierarchyid

Die meisten Strukturen werden heute mit Parent-Child dargestellt. Der einfachste Weg, eine Parent-Child-Struktur in eine Tabelle zu migrieren, die hierarchyid verwendet, führt über eine temporäre Spalte oder eine temporäre Tabelle, in der die Anzahl der Knoten auf jeder Ebene der Hierarchie festgehalten wird. Ein Beispiel für die Migration einer Parent-Child-Tabelle finden Sie in Lektion 1 von Lernprogramm: Verwenden des hierarchyid-Datentyps.

Transformationen von Abfragen für hierarchyid

Um die Leistung bei Abfragen von Hierarchien zu maximieren, führt SQL Server automatisch drei Transformationen von Abfragen aus, die hierarchyid-Werte betreffen. Das Ergebnis dieser Transformationen ist im Showplan für die transformierten Abfragen zu sehen.

"IsDescendantOf" wird zu einer Bereichssuche transformiert

Ist E als Spalte oder Variable gegeben, wird E.IsDescendantOf(c) in eine Bereichssuche umgewandelt. Dies reduziert wesentlich den Aufwand bei der Suche untergeordneter Elemente. Gibt es für E ein Tiefensuchindex, hilft diese Transformation, weil alle E untergeordneten Elemente nahe beieinander gespeichert sind. Beispielsweise wird der Codeausschnitt EmployeeId.IsDescendantOf(@value) als EmployeeId >= @Value AND EmployeeId <= @Value.DescendantLimit() ausgeführt. "DescendantLimit" ist eine interne Methode, die die Obergrenze aller für einen Knoten möglichen untergeordneten Elemente ermittelt. Beachten Sie, dass @value kein Parameter sein muss. Es könnte eine Spalte, vielleicht von einer Verknüpfungsbedingung, sein.

GetAncestor wird zu einem Bereichsscan und einem Residualprädikat transformiert

GetAncestor(n) gibt den n-ten Vorgänger eines Knotens an. Dies ist nützlich, wenn statt der allgemeineren Angabe IsDescendantOf die genaue Beziehung (übergeordnet, direkt oder indirekt untergeordnet usw.) zwischen zwei Knoten benötigt wird.

Führen Sie als Beispiel die folgende Abfrage aus, um alle Mitarbeiter zu suchen, deren direkter Vorgesetzter @value ist:

SELECT * FROM Employees WHERE EmployeeId.GetAncestor(1) = @value

Diese Anweisung wird in einen Bereichsscan für die @value untergeordneten Elemente mit dem ursprünglichen Prädikat als Residualprädikat transformiert. Der Code wird in die folgende Anweisung umgewandelt:

SELECT * FROM Employees 
WHERE 
   EmployeeId >= @Value AND EmployeeId <= @value.DescendantLimit() 
   AND EmployeeId.GetAncestor(1) = @value

Als Ergebnis dieser Transformation wird der Scan auf die @value untergeordnete Teilstruktur eingeschränkt.

GetAncestor wird in eine Indexsuche transformiert, die den Breitensuchindex verwendet.

Befindet sich bei der obigen Abfrage @value in den oberen Ebenen der Baumstruktur, dann wird die Zahl der durchsuchten Zeilen durch die obige Optimierung kaum reduziert. Wenn Abfragen nach dem n-ten Vorgänger häufig vorkommen, sollten Anwendungen, wie oben beschrieben, einen Breitensuchindex erstellen.

Wenn ein Breitensuchindex vorhanden ist, wird die oben erwähnte Abfrage weiter zu Folgendem transformiert:

SELECT * FROM Employees 
WHERE 
   EmployeeId >=@value AND EmployeeId <= @Value.DescendantLimit() 
   AND @value.GetLevel()+1 = EmployeeId.GetLevel()

Die letzte Zeile (die die GetLevel-Methoden enthält) führt eine Indexsuche im Breitensuchindex aus. Ist EmployeeId der Gruppierungsschlüssel, dann ist sie die zweite Spalte im Breitensuchindex, und die beiden Prädikate bilden eine Indexsuche, die exakt die n nahe beieinander gespeicherten direkten Nachkommen von @value angibt.

Die GetAncestor-Transformationen sind nicht auf Abfragen direkt übergeordneter Elemente beschränkt. Bei dem Argument für GetAncestor kann es sich um eine Variable oder eine Konstante handeln.

Siehe auch

Verweis

hierarchyid (Transact-SQL)

Konzepte

Arbeiten mit hierarchyid-Daten

hierarchyid-Datentyp-Methodenverweis

Lernprogramm: Verwenden des hierarchyid-Datentyps