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
ab
,a < b
znamená, žea
přichází předb
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á potomkaB
, a poté seA
odstraní aB
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');
Související úkoly
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