Sdílet prostřednictvím


Hierarchická data (SQL Server)

platí pro:SQL ServerAzure SQL DatabaseAzure SQL Managed InstanceSQL database v Microsoft Fabric

Zabudovaný datový typ hierarchyid usnadňuje ukládání a dotazování hierarchických dat. hierarchyid je optimalizovaný pro reprezentaci stromů, který je nejběžnější typ hierarchických dat.

Hierarchická data jsou definována jako sada datových položek, které spolu vzájemně souvisejí hierarchickými relacemi. Hierarchické relace existují tam, kde jedna položka dat je nadřazená jiné položce. Mezi příklady hierarchických dat běžně uložených v databázích patří následující položky:

  • Organizační struktura
  • Systém souborů
  • Sada úkolů v projektu
  • Taxonomie jazykových termínů
  • Graf odkazů mezi webovými stránkami

Pomocí datového typu hierarchyid můžete vytvářet tabulky s hierarchickou strukturou nebo popsat hierarchickou strukturu dat uložených v jiné lokaci. Pomocí funkcí hierarchii v Transact-SQL můžete dotazovat a spravovat hierarchická data.

Klíčové vlastnosti

Hodnota datového typu hierarchyid představuje pozici ve stromové hierarchii. Hodnoty hierarchyid mají následující vlastnosti:

  • Extrémně kompaktní

    Průměrný počet bitů potřebných k reprezentaci uzlu ve stromu s n uzly závisí na průměrném větvení (průměrný počet potomků uzlu). U malých rozvětvení (0–7) je velikost zhruba 6log{A}{n} bitů, kde A je průměrné rozvětvení. Jeden uzel v organizační hierarchii 100 000 lidí s průměrným rozvětvením šesti úrovní je reprezentován asi 38 bity. To je zaokrouhleno až na 40 bitů nebo 5 bajtů pro ukládání.

  • Porovnání je v podrobném pořadí.

    Vzhledem ke dvěma hierarchyid hodnotám a a b, a < b znamená, že a přichází před b při průchodu stromem do hloubky. Indexy na hierarchyid datových typů jsou v hloubkovém pořadí a uzly blízko sebe při hloubkovém procházení se ukládají poblíž sebe. Například potomci záznamu jsou uloženi vedle tohoto záznamu.

  • Podpora libovolných vložení a odstranění

    Použitím metody GetDescendant (databázový stroj) je vždy možné vygenerovat sourozence napravo od libovolného uzlu, vlevo od libovolného uzlu nebo mezi dvěma libovolnými uzly na stejné úrovni. Vlastnost porovnání se udržuje při vložení nebo odstranění libovolného počtu uzlů z hierarchie. Většina vložení a odstranění zachovává vlastnost kompaktnosti. Vložení mezi dva uzly však vytváří hodnoty hierarchyid s o něco méně kompaktní reprezentací.

Omezení

Datový typ hierarchyid má následující omezení:

  • Sloupec typu hierarchyid automaticky nepředstavuje strom. Je na aplikaci, aby vygenerovala a přiřadila hierarchyid hodnoty takovým způsobem, aby se požadovaný vztah mezi řádky projevil v hodnotách. Některé aplikace můžou mít sloupec typu hierarchyid, který označuje umístění v hierarchii definované v jiné tabulce.

  • Je na aplikaci, aby spravovala souběžnost při generování a přiřazování hodnot hierarchyid. Neexistuje žádná záruka, že hierarchyid hodnoty ve sloupci jsou jedinečné, pokud aplikace nepoužívá omezení jedinečného klíče nebo vynucuje jedinečnost sama prostřednictvím vlastní logiky.

  • Hierarchické relace reprezentované hodnotami typu hierarchyid se nevynucují podobně jako v relaci cizího klíče. Je možné a někdy vhodné mít hierarchický vztah, kdy A má potomka B, a poté se A odstraní a B má vztah k neexistujícímu záznamu. Pokud je toto chování nepřijatelné, musí se aplikace před odstraněním rodičů dotazovat na potomky.

Kdy použít alternativy k hierarchii

Existují dvě alternativy k hierarchyid pro reprezentaci hierarchických dat:

  • Rodič/dítě
  • XML

hierarchyid je obecně lepší než tyto alternativy. Existují však konkrétní situace, které jsou podrobně popsány v tomto článku, kde jsou alternativy pravděpodobně vyšší.

Rodič/dítě

Když použijete přístup nadřazený/podřízený, každý řádek obsahuje odkaz na nadřazeného. Následující tabulka definuje typickou tabulku, která slouží k uložení nadřazených a podřízených řádků v hierarchickém vztahu.

USE AdventureWorks2022;
GO

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

Porovnání hierarchie nadřazenosti/podřízenosti a hierarchyid pro běžné operace:

  • Dotazy na podstromy jsou výrazně rychlejší s hierarchií.
  • Dotazy přímých potomků jsou mírně pomalejší s hierarchyid.
  • Přesun ne-listových uzlů je pomalejší s hierarchyid .
  • Vkládání uzlů typu ne-list a vkládání nebo přesouvání uzlů typu list má stejnou složitost s id hierarchie.

Nadřazený/podřízený vztah může být vhodnější, pokud existují následující podmínky:

  • Velikost klíče je kritická. Pro stejný počet uzlů je hodnota hierarchyid rovná nebo větší než hodnota celé číselné rodiny (smallint, int, bigint). To je pouze důvod, proč ve výjimečných případech použít nadřazený/podřízený objekt, protože hierarchyid má výrazně lepší lokalitu výkonu vstupně-výstupních operací a složitost procesoru než běžné výrazy tabulek vyžadované při použití struktury nadřazenosti/podřízenosti.

  • Dotazy se zřídka dotazují napříč oddíly hierarchie. Jinými slovy, dotazy obvykle řeší pouze jeden bod v hierarchii. V těchto případech není kolokace důležitá. Například struktura nadřazený/podřízený je výhodnější, když se tabulka organizace používá pouze ke zpracování mzdy pro jednotlivé zaměstnance.

  • Ne-listové podstromy se často pohybují a jejich výkon je velmi důležitý. Změna umístění řádku v hierarchii v nadřazené nebo podřízené reprezentaci ovlivňuje jeden řádek. Změna umístění řádku v hierarchii má vliv na n řádků, kde n je počet uzlů v podstromu, který se přesouvá.

    Pokud se nepostižené podstromy často přesouvají a výkon je důležitý, ale většina těchto přesunů probíhá na dobře definované úrovni hierarchie, zvažte rozdělení vyšších a nižších úrovní do dvou samostatných hierarchií. To způsobuje, že se všechny pohyby přesunou na úrovně listů vyšší hierarchie. Představte si například hierarchii webů hostovaných službou. Weby obsahují mnoho stránek uspořádaných hierarchicky. Hostované weby se můžou přesunout do jiných umístění v hierarchii webu, ale podřízené stránky se zřídka mění jejich uspořádání. Toto může být reprezentováno prostřednictvím:

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

XML

Dokument XML je strom, a proto jedna instance datového typu XML může představovat úplnou hierarchii. Při vytvoření indexu XML se hodnoty hierarchyid používají interně k reprezentaci pozice v hierarchii.

Použití datového typu XML může být vyšší, pokud jsou splněny všechny následující podmínky:

  • Úplná hierarchie se vždy ukládá a načítá.
  • Aplikace data spotřebovávají ve formátu XML.
  • Vyhledávání predikátu jsou extrémně omezená a nejsou kritická pro výkon.

Pokud například aplikace sleduje více organizací, vždy ukládá a načítá úplnou organizační hierarchii a nevytváří dotaz do jedné organizace, může mít smysl tabulka s následujícím formulářem:

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

Strategie indexování pro hierarchická data

Existují dvě strategie indexování hierarchických dat:

  • Hloubkový

    Index s hloubkou ukládá řádky do podstromu blízko sebe. Například všichni zaměstnanci, kteří hlásí svému manažerovi, se ukládají blízko záznamů jejich manažerů.

    Ve hloubkovém indexu jsou všechny uzly v podstromu uzlu umístěny společně. Hloubkové indexy jsou proto efektivní pro odpovědi na dotazy na podstromy, například: "Najít všechny soubory v této složce a jejích podsložkách".

  • prohledávání do šířky

    Index první šířky ukládá řádky každé úrovně hierarchie dohromady. Například záznamy zaměstnanců, kteří přímo hlásí stejnému manažerovi, se ukládají blízko sebe.

    V šířkovém indexu jsou všechny přímé potomky uzlu na stejném místě. Indexy s popisem šířky jsou proto efektivní pro odpovědi na dotazy týkající se bezprostředních dětí, například: "Najít všechny zaměstnance, kteří hlásí přímo tomuto manažerovi"

Bez ohledu na to, zda použít vyhledávání do hloubky, do šířky, nebo obojí, a které z nich (pokud vůbec) nastavit jako klíč seskupení, závisí na relativní důležitosti výše uvedených typů dotazů a na relativní důležitosti operací SELECT oproti operacím DML. Podrobný příklad strategií indexování najdete v tématu Kurz: Použití datového typu hierarchyid.

Vytváření indexů

Metodu GetLevel() lze použít k vytvoření šířky prvního řazení. V následujícím příkladu se vytvoří indexy pro šířkové i hloubkové vyhledávání.

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

Příklady

Ukázky kódu Transact-SQL v tomto článku používají AdventureWorks2022 nebo AdventureWorksDW2022 ukázkovou databázi, kterou si můžete stáhnout z domovské stránky ukázky Microsoft SQL Serveru a projekty komunity.

Základní příklad

Následující příklad je záměrně zjednodušený, aby vám pomohl začít. Nejprve vytvořte tabulku pro uložení některých zeměpisných dat.

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

Teď vložte data pro některé kontinenty, země/oblasti, státy a města.

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');

Vyberte data a přidejte sloupec, který převede data úrovně na textovou hodnotu, která je snadno pochopitelná. Tento dotaz také seřadí výsledek podle datového typu hierarchyid.

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

Tady je sada výsledků.

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

Hierarchie má platnou strukturu, i když není interně konzistentní. Bahia je jediný stát. V hierarchii se zobrazuje jako rovný městu Brasilia. Podobně McMurdo Station nemá nadřazenou zemi nebo oblast. Uživatelé se musí rozhodnout, jestli je tento typ hierarchie vhodný pro jejich použití.

Přidejte další řádek a vyberte výsledky.

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];

To ukazuje více možných problémů. Kjóto lze vložit jako úroveň /1/3/1/, i když neexistuje žádná nadřazená úroveň /1/3/. A jak Londýn, tak i Kjóto mají stejnou hodnotu pro hierarchii. Uživatelé se znovu musí rozhodnout, jestli je tento typ hierarchie vhodný pro jejich použití, a blokovat hodnoty, které jsou pro jejich použití neplatné.

Tato tabulka také nepoužíla horní část hierarchie '/'. To bylo vynecháno, protože neexistuje žádný společný předek všech kontinentů. Můžete ho přidat přidáním celé planety.

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

Migrace z rodič/potomků na hierarchyid

Většina stromů je reprezentována pomocí nadřazeného/podřízeného objektu. Nejjednodušší způsob, jak migrovat z nadřazené nebo podřízené struktury do tabulky pomocí hierarchyid, je použít dočasný sloupec nebo dočasnou tabulku ke sledování počtu uzlů na každé úrovni hierarchie. Příklad migrace nadřazené/podřízené tabulky najdete v lekci 1 kurzu : Použití datového typu hierarchyid.

Správa stromu pomocí hierarchieID

I když sloupec hierarchyid nemusí nutně představovat strom, může aplikace snadno zajistit, že to udělá.

  • Při generování nových hodnot proveďte jeden z následujících kroků:

    • Sledujte číslo posledního potomka v nadřazeném řádku.
    • Vypočítá poslední dítě. K efektivnímu provádění tohoto postupu je zapotřebí šířkový index.
  • Vynucujte jedinečnost vytvořením jedinečného indexu ve sloupci, například jako součást klíče clusteringu. Pokud chcete zajistit vložení jedinečných hodnot, proveďte jeden z následujících kroků:

    • Detekujte porušení jedinečného klíče a proveďte opakování.
    • Určete jedinečnost každého nového podřízeného uzlu a vložte ho jako součást serializovatelné transakce.

Příklad použití detekce chyb

V následujícím příkladu vzorový kód vypočítá novou hodnotu prvku EmployeeId, potom zjistí jakékoli porušení klíče a vrátí se ke značce INS_EMP, aby přepočítal hodnotu EmployeeId pro nový řádek.

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

Příklad použití serializovatelné transakce

Index Org_BreadthFirst zajišťuje, že pro určení @last_child se používá vyhledávání v rozsahu. Kromě jiných chybových případů, kdy může aplikace chtít zkontrolovat, může po vložení dojít k porušení duplicitního klíče, což značí pokus o přidání více zaměstnanců se stejným ID, a proto @last_child musí být přepočítané. Následující kód vypočítá novou hodnotu uzlu v rámci serializovatelné transakce:

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;

Následující kód naplní tabulku třemi řádky a vrátí výsledky:

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

AddEmp 0x, 'Sariya'
GO

AddEmp 0x58, 'Mary'
GO

SELECT * FROM Org_T2

Tady je sada výsledků.

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

Vynucení stromu

Předchozí příklady ukazují, jak může aplikace zajistit zachování stromu. Pokud chcete strom vynutit pomocí omezení, počítaný sloupec, který definuje nadřazený objekt každého uzlu, se dá vytvořit s omezením cizího klíče zpět na ID primárního klíče.

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

Tato metoda vynucení relace se upřednostňuje, když kód, který není důvěryhodný pro údržbu hierarchického stromu, má přímý přístup DML k tabulce. Tato metoda však může snížit výkon, protože omezení musí být kontrolováno při každé operaci DML.

Vyhledání předků pomocí CLR

Běžná operace s dvěma uzly v hierarchii je nalezení jejich nejbližšího společného předka. Tuto úlohu lze zapsat v Transact-SQL nebo CLR, protože typ hierarchyid je k dispozici v obou. ClR se doporučuje, protože výkon je rychlejší.

Pomocí následujícího kódu CLR můžete zobrazit seznam předků a najít nejnižšího společného předka:

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;
    }
}

Pokud chcete použít ListAncestor a CommonAncestor metody v následujících příkladech Transact-SQL, sestavte knihovnu DLL a vytvořte sestavení HierarchyId_Operations v SQL Serveru spuštěním kódu podobného následujícímu příkladu:

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

Seznam předků

Vytvoření seznamu předků uzlu je běžnou operací, například zobrazení pozice v organizaci. Jedním ze způsobů, jak to udělat, je použití tabulkově hodnotové funkce pomocí třídy HierarchyId_Operations, definované dříve.

Použití jazyka Transact-SQL:

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

Příklad použití:

DECLARE @h 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

Najít nejnižšího společného předka

Pomocí dříve definované třídy HierarchyId_Operations vytvořte následující funkci Transact-SQL, která najde nejnižší společný nadřazený objekt zahrnující dva uzly v hierarchii:

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

Příklad použití:

DECLARE @h1 HIERARCHYID, @h2 HIERARCHYID;

SELECT @h1 = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = 'adventure-works\jossef0';-- Node is /1/1/3/

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

SELECT OrgNode.ToString() AS LogicalNode, LoginID
FROM HumanResources.EmployeeDemo
WHERE OrgNode = dbo.CommonAncestor(@h1, @h2);

Výsledný uzel je /1/1/

Přesuňte podstromy

Další běžnou operací je přesouvání podstromů. Následující postup vezme podstrom @oldMgr a přemění ho (včetně @oldMgr) na podstrom @newMgr.

CREATE PROCEDURE MoveOrg (
    @oldMgr NVARCHAR(256),
    @newMgr NVARCHAR(256)
)
AS
BEGIN
    DECLARE @nold HIERARCHYID, @nnew HIERARCHYID;

    SELECT @nold = OrgNode
    FROM HumanResources.EmployeeDemo
    WHERE LoginID = @oldMgr;

    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

    BEGIN TRANSACTION;

    SELECT @nnew = OrgNode
    FROM HumanResources.EmployeeDemo
    WHERE LoginID = @newMgr;

    SELECT @nnew = @nnew.GetDescendant(max(OrgNode), NULL)
    FROM HumanResources.EmployeeDemo
    WHERE OrgNode.GetAncestor(1) = @nnew;

    UPDATE HumanResources.EmployeeDemo
    SET OrgNode = OrgNode.GetReparentedValue(@nold, @nnew)
    WHERE OrgNode.IsDescendantOf(@nold) = 1;

    COMMIT TRANSACTION;
END;
GO