Dane hierarchiczne (SQL Server)

2025-05-20

Dotyczy:SQL Server Azure SQL Database Azure SQL Managed Instance SQL Database w Microsoft Fabric

Wbudowany typ danych hierarchyid ułatwia przechowywanie danych hierarchicznych i wykonywanie zapytań o nie. hierarchyid jest zoptymalizowany pod kątem reprezentowania drzew, które są najczęstszym typem danych hierarchicznych.

Dane hierarchiczne są definiowane jako zestaw elementów danych, które są ze sobą powiązane przez relacje hierarchiczne. Relacje hierarchiczne istnieją, gdy jeden element danych jest elementem nadrzędnym innego elementu. Przykłady danych hierarchicznych, które są często przechowywane w bazach danych, obejmują następujące elementy:

Struktura organizacyjna
System plików
Zestaw zadań w projekcie
Taksonomia terminów językowych
Wykres łączy między stronami sieci Web

Użyj hierarchyid jako typu danych, aby utworzyć tabele ze strukturą hierarchiczną lub opisać hierarchiczną strukturę danych przechowywanych w innej lokalizacji. Użyj funkcji hierarchyid w Transact-SQL, aby wykonywać zapytania dotyczące danych hierarchicznych i zarządzać nimi.

Kluczowe właściwości

Wartość hierarchyid typ danych reprezentuje pozycję w hierarchii drzewa. Wartości hierarchyid mają następujące właściwości:

Bardzo kompaktowy

Średnia liczba bitów wymaganych do reprezentowania węzła w drzewie z n węzłów zależy od średniego fanoutu (średniej liczby elementów podrzędnych węzła). W przypadku małych fanoutów (0–7) rozmiar wynosi około $6log{A}{n}$ bitów, gdzie A jest średnim fanoutem. Węzeł w hierarchii organizacyjnej liczącej 100 000 osób, z średnią rozpiętością sześciu poziomów, zajmuje około 38 bitów. Jest to zaokrąglane do 40 bitów lub 5 bajtów dla magazynu.
Porównanie jest w pierwszej kolejności

Biorąc pod uwagę dwie wartości hierarchyida i b, a < b oznacza, że a jest przed b w trasie przeszukiwania drzewa w głąb. Indeksy w hierarchii typy danych są w pierwszej kolejności, a węzły blisko siebie w głębi pierwszego przechodzenia są przechowywane w pobliżu siebie. Na przykład dzieci rekordu są przechowywane obok tego rekordu.
Obsługa dowolnych wstawiania i usuwania

Za pomocą metody GetDescendant (aparatu bazy danych) zawsze można wygenerować element równorzędny po prawej stronie dowolnego węzła, z lewej strony dowolnego węzła lub między dwoma elementami równorzędnymi. Właściwość porównania jest zachowywana, gdy dowolna liczba węzłów zostanie wstawiona lub usunięta z hierarchii. Większość wstawiania i usuwania zachowuje właściwość kompaktowania. Jednak wstawienia między dwoma węzłami generują wartości hierarchyid z nieco mniej zwartą reprezentacją.

Ograniczenia

Typ danych hierarchyid ma następujące ograniczenia:

Kolumna typu hierarchyid nie reprezentuje automatycznie drzewa. Do aplikacji należy generowanie i przypisywanie wartości hierarchyid w taki sposób, aby żądana relacja między wierszami została odzwierciedlona w wartościach. Niektóre aplikacje mogą mieć kolumnę typu hierarchyid, która wskazuje lokalizację w hierarchii zdefiniowanej w innej tabeli.
Do aplikacji należy zarządzanie współbieżnością podczas generowania i przypisywania wartości hierarchyid . Nie ma gwarancji, że wartości hierarchyid w kolumnie są unikatowe, chyba że aplikacja używa unikatowego ograniczenia klucza lub wymusza unikatowość za pomocą własnej logiki.
Relacje hierarchiczne, które są reprezentowane przez wartości hierarchyid, nie są egzekwowane jak relacje klucza obcego. Istnieje możliwość, a czasami jest to odpowiednie, aby mieć relację hierarchiczną, gdzie A ma podrzędny element B, a następnie A jest usunięty, pozostawiając B z relacją do nieistniejącego rekordu. Jeśli takie zachowanie jest niedopuszczalne, aplikacja musi wykonywać zapytania dotyczące potomków przed usunięciem rodziców.

Kiedy należy używać alternatyw dla hierarchyid

Dwie alternatywy dla hierarchiiid reprezentujące dane hierarchiczne to:

Rodzic/dziecko
XML

hierarchyid jest ogólnie lepszy od tych alternatyw. Jednak istnieją konkretne sytuacje, szczegółowo opisane w tym artykule, gdzie alternatywy są prawdopodobnie lepsze.

Rodzic/dziecko

W przypadku korzystania z podejścia nadrzędnego/podrzędnego każdy wiersz zawiera odwołanie do elementu nadrzędnego. W poniższej tabeli zdefiniowano typową tabelę, która zawiera wiersze nadrzędne i podrzędne w relacji nadrzędnej/podrzędnej:

USE AdventureWorks2022;
GO

CREATE TABLE ParentChildOrg (
    BusinessEntityID INT PRIMARY KEY,
    ManagerId INT FOREIGN KEY REFERENCES ParentChildOrg(BusinessEntityID),
    EmployeeName NVARCHAR(50)
);
GO

Porównanie relacji nadrzędny/podrzędny i hierarchyid dla typowych operacji:

Zapytania poddrzewa są znacznie szybsze dzięki hierarchyidowi.
Zapytania dotyczące bezpośrednich potomków są nieco wolniejsze z hierarchyid.
Przenoszenie węzłów nie-liściastych jest wolniejsze z hierarchyid.
Wstawianie węzłów innych niż liście oraz wstawianie lub przenoszenie węzłów liścia mają taką samą złożoność jak hierarchyid.

Relacja rodzic/dziecko może być lepsza, gdy istnieją następujące warunki:

Rozmiar klucza jest krytyczny. W przypadku tej samej liczby węzłów wartość hierarchyid jest równa lub większa niż wartość rodziny całkowitej (smallint, int, bigint). Jest to tylko powód używania struktury nadrzędnej/podrzędnej w rzadkich przypadkach, ponieważ hierarchyid ma znacznie lepszą lokalność operacji wejścia/wyjścia oraz złożoność procesora niż typowe wyrażenia tabel, które trzeba stosować przy strukturze nadrzędnej/podrzędnej.
Zapytania rzadko wykonują zapytania między poziomami hierarchii. Innymi słowy zapytania zwykle dotyczą tylko jednego punktu w hierarchii. W takich przypadkach kolokacja nie jest ważna. Na przykład relacja nadrzędny/podrzędny jest bardziej efektywna, gdy tabela organizacji jest używana tylko do przetwarzania listy płac dla poszczególnych pracowników.
Poddrzewa nienastawne są często przenoszone, a wydajność jest bardzo ważna. W reprezentacji nadrzędnej/podrzędnej zmiana lokalizacji wiersza w hierarchii ma wpływ na pojedynczy wiersz. Zmiana lokalizacji wiersza w użyciu hierarchyid ma wpływ na n wierszy, gdzie n jest liczbą węzłów w poddrzewie przenoszonym.

Jeśli poddrzewa wewnętrzne są często przenoszone i jeśli wydajność ma znaczenie, ale duża część z nich następuje na dobrze zdefiniowanym poziomie hierarchii, można rozważyć podział wyższych i niższych poziomów na dwie hierarchie. To sprawia, że wszystkie ruchy przenoszą się na poziomy liści wewnątrz wyższej hierarchii. Rozważmy na przykład hierarchię witryn sieci Web hostowanych przez usługę. Witryny zawierają wiele stron rozmieszczonych w sposób hierarchiczny. Hostowane witryny mogą być przenoszone do innych lokalizacji w hierarchii lokacji, ale strony podrzędne są rzadko zmieniane. Może to być reprezentowane za pośrednictwem:
```
CREATE TABLE HostedSites (
    SiteId HIERARCHYID,
    PageId HIERARCHYID
);
GO
```

XML

Dokument XML jest drzewem, dlatego pojedyncze wystąpienie typu danych XML może reprezentować pełną hierarchię. W programie SQL Server po utworzeniu indeksu XML wartości hierarchyid są używane wewnętrznie do reprezentowania pozycji w hierarchii.

Użycie typu danych XML może być lepsze, jeśli spełnione są wszystkie następujące warunki:

Pełna hierarchia jest zawsze przechowywana i pobierana.
Dane są używane w formacie XML przez aplikację.
Wyszukiwanie predykatów jest bardzo ograniczone i nie jest krytyczne dla wydajności.

Jeśli na przykład aplikacja śledzi wiele organizacji, zawsze przechowuje i pobiera pełną hierarchię organizacyjną i nie wykonuje zapytań w jednej organizacji, tabela następującego formularza może mieć sens:

CREATE TABLE XMLOrg (
    Orgid INT,
    Orgdata XML
);
GO

Strategie indeksowania dla danych hierarchicznych

Istnieją dwie strategie indeksowania danych hierarchicznych:

Głębokość pierwsza

Indeks szczegółowy przechowuje wiersze w poddrzewie w pobliżu siebie. Na przykład wszyscy pracownicy, którzy raportują bezpośrednio do menedżera, są przechowywani w pobliżu rekordu ich menedżera.

W szczegółowym indeksie wszystkie węzły w poddrzewie węzła są kolokowane. W związku z tym indeksy szczegółowe są wydajne w przypadku odpowiadania na zapytania dotyczące poddrzew, takich jak: "Znajdź wszystkie pliki w tym folderze i jego podfolderach"
Przeszukiwanie wszerz

Indeks przeganiający w poziomie przechowuje wiersze z każdego poziomu hierarchii razem. Na przykład rekordy pracowników, którzy bezpośrednio raportują do tego samego menedżera, są przechowywane w pobliżu siebie.

W indeksie po raz pierwszy wszystkie bezpośrednie elementy podrzędne węzła są kolokowane. Ze względu na to indeksy przeszukiwania wszerz są wydajne do odpowiadania na zapytania dotyczące bezpośrednich dzieci, takich jak: "Znajdź wszystkich pracowników podlegających bezpośredniemu menedżerowi"

Decyzja o wyborze podejścia przeszukiwania wszerz, w głąb lub obu oraz którym podejściu przydzielić klucz klastrowania (jeśli w ogóle) zależy od względnego znaczenia powyższych typów zapytań oraz względnego znaczenia SELECT w porównaniu do operacji DML. Aby zapoznać się ze szczegółowym przykładem strategii indeksowania, zobacz Samouczek: używanie typu danych hierarchyid.

Tworzenie indeksów

Metodę GetLevel() można użyć do utworzenia zakresu pierwszej kolejności. W poniższym przykładzie tworzone są zarówno indeksy przeszukiwania wszerz, jak i przeszukiwania w głąb.

USE AdventureWorks2022;
GO

CREATE TABLE Organization (
    BusinessEntityID HIERARCHYID,
    OrgLevel AS BusinessEntityID.GetLevel(),
    EmployeeName NVARCHAR(50) NOT NULL
);
GO

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

CREATE UNIQUE INDEX Org_Depth_First
ON Organization (BusinessEntityID);
GO

Przykłady

Przykłady kodu w tym artykule korzystają z przykładowej bazy danych AdventureWorks2022 lub AdventureWorksDW2022, którą można pobrać ze strony głównej Przykładów programu Microsoft SQL Server i projektów społeczności.

Przykład podstawowy

Poniższy przykład jest celowo uproszczony, aby ułatwić rozpoczęcie pracy. Najpierw utwórz tabelę do przechowywania niektórych danych geograficznych.

CREATE TABLE BasicDemo (
    [Level] HIERARCHYID NOT NULL,
    Location NVARCHAR(30) NOT NULL,
    LocationType NVARCHAR(9) NULL
);

Teraz wstaw dane dla niektórych kontynentów, krajów/regionów, stanów i miast.

INSERT BasicDemo
VALUES ('/1/', 'Europe', 'Continent'),
    ('/2/', 'South America', 'Continent'),
    ('/1/1/', 'France', 'Country'),
    ('/1/1/1/', 'Paris', 'City'),
    ('/1/2/1/', 'Madrid', 'City'),
    ('/1/2/', 'Spain', 'Country'),
    ('/3/', 'Antarctica', 'Continent'),
    ('/2/1/', 'Brazil', 'Country'),
    ('/2/1/1/', 'Brasilia', 'City'),
    ('/2/1/2/', 'Bahia', 'State'),
    ('/2/1/2/1/', 'Salvador', 'City'),
    ('/3/1/', 'McMurdo Station', 'City');

Wybierz dane, dodając kolumnę, która konwertuje dane na wartość tekstową, którą można łatwo zrozumieć. To zapytanie porządkuje również wynik według typu danych hierarchyid .

SELECT CAST([Level] AS NVARCHAR(100)) AS [Converted Level],
    *
FROM BasicDemo
ORDER BY [Level];

Oto zestaw wyników.

Converted Level  Level     Location         LocationType
---------------  --------  ---------------  ---------------
/1/              0x58      Europe           Continent
/1/1/            0x5AC0    France           Country
/1/1/1/          0x5AD6    Paris            City
/1/2/            0x5B40    Spain            Country
/1/2/1/          0x5B56    Madrid           City
/2/              0x68      South America    Continent
/2/1/            0x6AC0    Brazil           Country
/2/1/1/          0x6AD6    Brasilia         City
/2/1/2/          0x6ADA    Bahia            State
/2/1/2/1/        0x6ADAB0  Salvador         City
/3/              0x78      Antarctica       Continent
/3/1/            0x7AC0    McMurdo Station  City

Hierarchia ma prawidłową strukturę, mimo że nie jest spójna wewnętrznie. Bahia jest jedynym stanem. Pojawia się w hierarchii jako element równorzędny miasta Brasilia. Podobnie stacja McMurdo nie ma kraju/regionu nadrzędnego. Użytkownicy muszą zdecydować, czy ten typ hierarchii jest odpowiedni do ich użycia.

Dodaj kolejny wiersz i wybierz wyniki.

INSERT BasicDemo
VALUES ('/1/3/1/', 'Kyoto', 'City'),
    ('/1/3/1/', 'London', 'City');

SELECT CAST([Level] AS NVARCHAR(100)) AS [Converted Level],
    *
FROM BasicDemo
ORDER BY [Level];

Pokazuje to więcej możliwych problemów. Kioto można wstawić jako poziom /1/3/1/ , mimo że nie ma poziomu /1/3/nadrzędnego . Zarówno Londyn, jak i Kioto mają tę samą wartość dla hierarchyid. Ponownie użytkownicy muszą zdecydować, czy tego typu hierarchia jest odpowiednia do ich użycia, oraz zablokować wartości, które są niewłaściwe dla ich zastosowania.

Ponadto ta tabela nie korzystała z górnej części hierarchii '/'. Pominięto go, ponieważ nie ma jednego wspólnego przodka kontynentów. Możesz dodać jedną, dodając całą planetę.

INSERT BasicDemo
VALUES ('/', 'Earth', 'Planet');

Migrowanie z modelu rodzic/dziecko do hierarchyid

Większość drzew jest reprezentowana przy użyciu struktury nadrzędnej/podrzędnej. Najprostszym sposobem migracji ze struktury nadrzędny/podrzędny do tabeli przy użyciu hierarchyid jest skorzystanie z kolumny tymczasowej lub tabeli tymczasowej do śledzenia liczby węzłów na każdym poziomie hierarchii. Aby zapoznać się z przykładem migracji tabeli nadrzędnej/podrzędnej, zobacz część 1 Samouczka: używanie hierarchyid typu danych.

Zarządzanie drzewem przy użyciu hierarchyid

Chociaż kolumna hierarchyid nie musi reprezentować drzewa, aplikacja może łatwo upewnić się, że to zrobi.

Podczas generowania nowych wartości wykonaj jedną z następujących czynności:
- Śledź ostatni numer dziecka w wierszu rodzica.
- Oblicz ostatnie dziecko. Skuteczne wykonanie tej czynności wymaga indeksu przeszukiwania wszerz.
Wymuś unikatowość, tworząc unikatowy indeks w kolumnie, być może jako część klucza klastrowania. Aby upewnić się, że wstawiane są unikatowe wartości, wykonaj jedną z następujących czynności:
- Wykryj błędy naruszenia unikalnego klucza i ponów próbę.
- Określ unikatowość każdego nowego węzła podrzędnego i wstaw go w ramach transakcji możliwej do serializacji.

Przykład użycia wykrywania błędów

W poniższym przykładzie kod testowy oblicza nową wartość elementu podrzędnego EmployeeId, a następnie wykrywa naruszenie klucza i powraca do znacznika INS_EMP, aby ponownie obliczyć wartość EmployeeId dla nowego wiersza.

USE AdventureWorks;
GO

CREATE TABLE Org_T1 (
    EmployeeId HIERARCHYID PRIMARY KEY,
    OrgLevel AS EmployeeId.GetLevel(),
    EmployeeName NVARCHAR(50)
);
GO

CREATE INDEX Org_BreadthFirst ON Org_T1 (
    OrgLevel,
    EmployeeId
);
GO

CREATE PROCEDURE AddEmp (
    @mgrid HIERARCHYID,
    @EmpName NVARCHAR(50)
)
AS
BEGIN
    DECLARE @last_child HIERARCHYID;

    INS_EMP:

    SELECT @last_child = MAX(EmployeeId)
    FROM Org_T1
    WHERE EmployeeId.GetAncestor(1) = @mgrid;

    INSERT INTO Org_T1 (EmployeeId, EmployeeName)
    SELECT @mgrid.GetDescendant(@last_child, NULL), @EmpName;

    -- On error, return to INS_EMP to recompute @last_child
    IF @@error <> 0
        GOTO INS_EMP
END;
GO

Przykład użycia transakcji możliwej do serializacji

Indeks Org_BreadthFirst zapewnia, że definicja @last_child korzysta z wyszukiwania w zakresie. Oprócz innych przypadków błędów aplikacja może chcieć sprawdzić, zduplikowane naruszenie klucza po wstawieniu wskazuje próbę dodania wielu pracowników o tym samym identyfikatorze i dlatego @last_child należy ponownie skompilować. Poniższy kod oblicza nową wartość węzła w ramach transakcji możliwej do serializacji:

CREATE TABLE Org_T2 (
    EmployeeId HIERARCHYID PRIMARY KEY,
    LastChild HIERARCHYID,
    EmployeeName NVARCHAR(50)
);
GO

CREATE PROCEDURE AddEmp (
    @mgrid HIERARCHYID,
    @EmpName NVARCHAR(50)
)
AS
BEGIN
    DECLARE @last_child HIERARCHYID;

    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

    BEGIN TRANSACTION;

    SELECT @last_child = EmployeeId.GetDescendant(LastChild, NULL)
    FROM Org_T2
    WHERE EmployeeId = @mgrid;

    UPDATE Org_T2
    SET LastChild = @last_child
    WHERE EmployeeId = @mgrid;

    INSERT Org_T2 (EmployeeId, EmployeeName)
    VALUES (@last_child, @EmpName);

    COMMIT;
END;

Poniższy kod wypełnia tabelę trzema wierszami i zwraca wyniki:

INSERT Org_T2 (EmployeeId, EmployeeName)
VALUES (HIERARCHYID::GetRoot(), 'David');
GO

EXECUTE AddEmp 0x, 'Sariya';
GO

EXECUTE AddEmp 0x58, 'Mary';
GO

SELECT * FROM Org_T2

Oto zestaw wyników.

EmployeeId LastChild EmployeeName
---------- --------- ------------
0x        0x58       David
0x58      0x5AC0     Sariya
0x5AC0    NULL       Mary

Wymuszanie drzewa

W poprzednich przykładach pokazano, jak aplikacja może zapewnić utrzymanie drzewa. Aby wymusić strukturę drzewa przy użyciu ograniczeń, można stworzyć obliczoną kolumnę, która definiuje element nadrzędny każdego węzła, z ograniczeniem klucza obcego odnoszącym się z powrotem do identyfikatora klucza podstawowego.

CREATE TABLE Org_T3 (
    EmployeeId HIERARCHYID PRIMARY KEY,
    ParentId AS EmployeeId.GetAncestor(1) PERSISTED FOREIGN KEY REFERENCES Org_T3(EmployeeId),
    LastChild HIERARCHYID,
    EmployeeName NVARCHAR(50)
);
GO

Ta metoda wymuszania relacji jest preferowana, gdy kod, któremu nie można zaufać w kwestii zarządzania drzewem hierarchicznym, ma bezpośredni dostęp DML do tabeli. Jednak ta metoda może zmniejszyć wydajność, ponieważ ograniczenie musi być sprawdzane dla każdej operacji DML.

Znajdowanie przodków przy użyciu środowiska CLR

Typową operacją obejmującą dwa węzły w hierarchii jest znalezienie najniższego wspólnego przodka. To zadanie można napisać w Transact-SQL lub CLR, ponieważ typ hierarchyid jest dostępny w obu tych przypadkach. Zaleca się użycie środowiska CLR, ponieważ wydajność jest szybsza.

Użyj następującego kodu CLR, aby wyświetlić listę przodków i znaleźć najniższego wspólnego przodka.

using System;
using System.Collections;
using System.Text;
using Microsoft.SqlServer.Server; // SqlFunction Attribute
using Microsoft.SqlServer.Types;  // SqlHierarchyId

public partial class HierarchyId_Operations
{
    [SqlFunction(FillRowMethodName = "FillRow_ListAncestors")]
    public static IEnumerable ListAncestors(SqlHierarchyId h)
    {
        while (!h.IsNull)
        {
            yield return (h);
            h = h.GetAncestor(1);
        }
    }

    public static void FillRow_ListAncestors(
        Object obj,
        out SqlHierarchyId ancestor
    )
    {
        ancestor = (SqlHierarchyId)obj;
    }

    public static HierarchyId CommonAncestor(
        SqlHierarchyId h1,
        HierarchyId h2
    )
    {
        while (!h1.IsDescendantOf(h2))
        {
            h1 = h1.GetAncestor(1);
        }

        return h1;
    }
}

Aby użyć metody ListAncestor i CommonAncestor w następujących przykładach Transact-SQL, skompiluj bibliotekę DLL i utwórz zestaw HierarchyId_Operations na serwerze SQL przez wykonanie następującego przykładu kodu.

CREATE ASSEMBLY HierarchyId_Operations
    FROM '<path to DLL>\ListAncestors.dll';
GO

Lista przodków

Tworzenie listy elementów podrzędnych węzła jest wspólną operacją, na przykład w celu pokazania pozycji w organizacji. Jednym ze sposobów wykonania tej czynności jest użycie funkcji table-valued przy użyciu wcześniej zdefiniowanej klasy HierarchyId_Operations.

Korzystanie z języka Transact-SQL:

CREATE FUNCTION ListAncestors (@node HIERARCHYID)
RETURNS TABLE (node HIERARCHYID)
AS
EXTERNAL NAME HierarchyId_Operations.HierarchyId_Operations.ListAncestors;
GO

Przykład użycia:

DECLARE @h AS HIERARCHYID;

SELECT @h = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = 'adventure-works\janice0' -- /1/1/5/2/

SELECT LoginID,
    OrgNode.ToString() AS LogicalNode
FROM HumanResources.EmployeeDemo AS ED
INNER JOIN ListAncestors(@h) AS A
    ON ED.OrgNode = A.Node
GO

Znajdowanie najniższego wspólnego przodka

Korzystając z klasy zdefiniowanej HierarchyId_Operations wcześniej, utwórz następującą funkcję Transact-SQL, aby znaleźć najniższy wspólny element nadrzędny obejmujący dwa węzły w hierarchii:

CREATE FUNCTION CommonAncestor (
    @node1 HIERARCHYID,
    @node2 HIERARCHYID
)
RETURNS HIERARCHYID
AS
EXTERNAL NAME HierarchyId_Operations.HierarchyId_Operations.CommonAncestor;
GO