Hierarkiska data (SQL Server)

2025-05-20

Gäller för:SQL Server Azure SQL Database Azure SQL Managed Instance SQL-databas i Microsoft Fabric

Den inbyggda datatypen hierarchyid gör det enklare att lagra och fråga efter hierarkiska data. hierarchyid är optimerat för att representera träd, som är den vanligaste typen av hierarkiska data.

Hierarkiska data definieras som en uppsättning dataobjekt som är relaterade till varandra av hierarkiska relationer. Hierarkiska relationer finns där ett dataobjekt är överordnat till ett annat objekt. Exempel på hierarkiska data som vanligtvis lagras i databaser är följande objekt:

En organisationsstruktur
Ett filsystem
En uppsättning aktiviteter i ett projekt
En taxonomi av språktermer
Ett diagram över länkar mellan webbsidor

Använd hierarchyid som datatyp för att skapa tabeller med en hierarkisk struktur eller för att beskriva den hierarkiska strukturen för data som lagras på en annan plats. Använd funktionerna hierarchyid i Transact-SQL för att fråga och hantera hierarkiska data.

Nyckelegenskaper

Ett värde för hierarchyid datatyp representerar en position i en trädhierarki. Värden för hierarchyid ha följande egenskaper:

Extremt kompakt

Det genomsnittliga antalet bitar som krävs för att representera en nod i ett träd med n noder beror på den genomsnittliga utfläkten (det genomsnittliga antalet underordnade noder). För små fanouts (0–7) är storleken cirka $6log{A}{n}$ bitar, där A är den genomsnittliga fanouten. En nod med en genomsnittlig fanout på sex nivåer i en organisationshierarki med 100 000 personer tar cirka 38 bitar. Detta avrundas upp till 40 bitar, eller 5 byte, för lagring.
Jämförelsen är i djupordning

Givet två hierarchyid-värdena och b betyder a < b att a kommer före b i en djup-först genomlöpning av trädet. Index på hierarkiid datatyper är i djupordning, och noder nära varandra i en djup-första bläddering lagras nära varandra. Till exempel lagras poster som tillhör en post bredvid den.
Stöd för godtyckliga infogningar och borttagningar

Med metoden GetDescendant (Databasmotor) är det alltid möjligt att generera ett syskon till höger om en viss nod, till vänster om en viss nod eller mellan två syskon. Jämförelseegenskapen bibehålls när ett godtyckligt antal noder infogas eller tas bort från hierarkin. De flesta infogningar och borttagningar bevarar kompakthetsegenskapen. Infogningar mellan två noder ger dock hierarkiidvärden med en något mindre kompakt representation.

Begränsningar

Datatypen hierarchyid har följande begränsningar:

En kolumn av typen hierarchyid representerar inte automatiskt ett träd. Det är upp till programmet att generera och tilldela hierarkiidvärden på ett sådant sätt att den önskade relationen mellan rader återspeglas i värdena. Vissa program kan ha en kolumn av typen hierarchyid som anger platsen i en hierarki som definierats i en annan tabell.
Det är upp till programmet att hantera samtidighet när det gäller att generera och tilldela hierarkiidvärden . Det finns ingen garanti för att hierarchyid-värden i en kolumn är unika om inte programmet använder en unik nyckelbegränsning eller framtvingar unikhet genom sin egen logik.
Hierarkiska relationer som representeras av hierarki-id-värden upprätthålls inte som en främmande nyckelrelation. Det är möjligt, och ibland lämpligt, att ha en hierarkisk relation där A har ett underordnat B, och sedan tas A bort vilket lämnar B med en relation till en obefintlig post. Om det här beteendet är oacceptabelt måste programmet kontrollera efter underordnade innan det tar bort överordnade.

När du ska använda alternativ till hierarchyid

Två alternativ till hierarchyid för att representera hierarkiska data är:

Förälder/barn
XML

hierarchyid är vanligtvis överlägsen dessa alternativ. Det finns dock specifika situationer, som beskrivs i den här artikeln, där alternativen sannolikt är överlägsna.

Förälder/barn

När du använder metoden överordnad/underordnad innehåller varje rad en referens till den överordnade. I följande tabell definieras en typisk tabell som används för att innehålla de överordnade och underordnade raderna i en överordnad/underordnad relation:

USE AdventureWorks2022;
GO

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

Jämförelse av överordnad/underordnad och hierarkiid för vanliga åtgärder:

Subträdfrågor går betydligt snabbare med hierarchyid.
Direkta underordnade frågor är något långsammare med hierarchyid.
Det går långsammare att flytta noder utan blad med hierarchyid.
Att infoga noder som inte är bladnoder och infoga eller flytta lövnoder har samma komplexitet som hierarchyid.

Förälder/barn kan vara fördelaktig när följande villkor finns:

Nyckelns storlek är kritisk. För samma antal noder är ett hierarchyid-värde lika med eller större än ett heltals-familjevärde (smallint, int, bigint). Det finns bara en anledning att använda en föräldra-/barn-struktur i sällsynta fall, eftersom hierarchyid har betydligt bättre lokalitet för I/O och CPU-komplexitet än de vanliga tabelluttryck som krävs vid användning av en föräldra-/barn-struktur.
Sökningar sker sällan över sektioner av hierarkin. Med andra ord hanterar frågor vanligtvis bara en enda punkt i hierarkin. I dessa fall är samlokalisering inte viktigt. Som exempel är "överordnad/underordnad"-strukturen att föredra när organisationstabellen endast används för att bearbeta löner för enskilda anställda.
Icke-bladunderträd flyttas ofta och prestanda är mycket viktig. Om du ändrar platsen för en rad i en hierarki påverkar det en enskild rad i en överordnad/underordnad representation. Om du ändrar platsen för en rad i en hierarchyid-användning påverkas n rader, där n är antalet noder i underträdet som flyttas.

Om de icke-bladiga underträden flyttas ofta och prestanda är viktigt för dig, men om de flesta flyttningar sker på en väldefinierad nivå i hierarkin, bör du överväga att dela upp de högre och lägre nivåerna i två separata hierarkier. Detta gör att alla flyttar till lövnivåer i den högre hierarkin. Överväg till exempel en hierarki med webbplatser som hanteras av en tjänst. Webbplatser innehåller många sidor ordnade på ett hierarkiskt sätt. Värdbaserade sajter kan flyttas till andra platser i webbplatsstrukturen, men de underordnade sidorna omorganiseras sällan. Detta kan representeras via:
```
CREATE TABLE HostedSites (
    SiteId HIERARCHYID,
    PageId HIERARCHYID
);
GO
```

XML

Ett XML-dokument är ett träd och därför kan en enda XML-datatypinstans representera en fullständig hierarki. I SQL Server när ett XML-index skapas används hierarkiidvärden internt för att representera positionen i hierarkin.

Att använda XML-datatyp kan vara överlägset när alla följande är sanna:

Den fullständiga hierarkin lagras och hämtas alltid.
Data används i XML-format av programmet.
Predikatsökningar är extremt begränsade och inte prestandakritiska.

Om ett program till exempel spårar flera organisationer, alltid lagrar och hämtar hela organisationshierarkin och inte frågar i en enda organisation, kan en tabell med följande formulär vara meningsfull:

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

Indexstrategier för hierarkiska data

Det finns två strategier för indexering av hierarkiska data:

Djupet först

Ett djupindex lagrar raderna i ett underträd nära varandra. Till exempel lagras alla anställda som rapporterar via en chef nära sina chefers poster.

I ett djupförst index är alla noder i underträdets av en nod grupperade tillsammans. Djupindex är därför effektiva för att besvara frågor om underträd, till exempel: "Hitta alla filer i den här mappen och dess undermappar"
Bredden-först

Ett breddindex lagrar raderna på varje nivå i hierarkin. Till exempel lagras poster för anställda som direkt rapporterar till samma chef nära varandra.

I ett bredden-första index placeras alla direkta barn till en nod tillsammans. Breddsorteringsindex är därför effektiva för att besvara frågor om direkta underordnade, till exempel: "Hitta alla anställda som rapporterar direkt till den här chefen."

Huruvida du ska använda djup-först, bredd-först eller båda, och vad som ska vara klustringsnyckel (om någon), beror på den relativa betydelsen av de ovanstående frågetyperna och den relativa betydelsen av SELECT jämfört med DML-åtgärder. Ett detaljerat exempel på indexeringsstrategier finns i Självstudie: Använda datatypen hierarchyid.

Skapa index

Metoden GetLevel() kan användas för att skapa en bredd-först ordning. I följande exempel skapas både breddprioriterade och djupprioriterade index:

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

Exempel

Kodexemplen i den här artikeln använder AdventureWorks2022- eller AdventureWorksDW2022-exempeldatabasen, som du kan ladda ned från startsidan Microsoft SQL Server Samples och Community Projects.

Grundläggande exempel

Följande exempel är avsiktligt förenklat för att hjälpa dig att komma igång. Skapa först en tabell för att lagra vissa geografiska data.

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

Infoga nu data för vissa kontinenter, länder/regioner, stater och städer.

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

Välj data och lägg till en kolumn som konverterar nivådata till ett textvärde som är lätt att förstå. Den här frågan beställer också resultatet efter datatypen hierarchyid .

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

Här är resultatet.

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

Hierarkin har en giltig struktur, även om den inte är internt konsekvent. Bahia är den enda staten. Den visas i hierarkin som en motsvarighet till staden Brasilia. På samma sätt har McMurdo Station inget överordnat land/region. Användarna måste bestämma om den här typen av hierarki är lämplig för deras användning.

Lägg till ytterligare en rad och välj resultatet.

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

Detta visar på fler möjliga problem. Kyoto kan infogas som nivå /1/3/1/ även om det inte finns någon överordnad nivå /1/3/. Och både London och Kyoto har samma värde för hierarkiid. Återigen måste användarna bestämma om den här typen av hierarki är lämplig för deras användning och blockera värden som är ogiltiga för deras användning.

Den här tabellen använde inte toppen av hierarkin '/'. Det utelämnades eftersom det inte finns någon gemensam förälder till alla kontinenter. Du kan lägga till en genom att lägga till hela planeten.

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

Migrera från föräldra-barn till hierarchyid

De flesta träd representeras med förälder/barn. Det enklaste sättet att migrera från en överordnad/underordnad struktur till en tabell med hjälp av hierarchyid är att använda en tillfällig kolumn eller en tillfällig tabell för att hålla reda på antalet noder på varje nivå i hierarkin. Ett exempel på migrering av en överordnad/underordnad tabell finns i lektion 1 i Självstudie: Använda datatypen hierarchyid.

Hantera ett träd med hjälp av hierarchyid

Även om en hierarchyid-kolumn inte nödvändigtvis representerar ett träd, kan ett program enkelt se till att det gör det.

Gör något av följande när du genererar nya värden:
- Håll reda på det sista barnnumret i den överordnade raden.
- Beräkna det sista barnet. För att göra detta effektivt krävs ett bredd-första index.
Framtvinga unikhet genom att skapa ett unikt index i kolumnen, kanske som en del av en klustringsnyckel. Gör något av följande för att säkerställa att unika värden infogas:
- Identifiera fel med unik nyckelöverträdelse och försök igen.
- Fastställ unikheten för varje ny underordnad nod och infoga den som en del av en serialiserbar transaktion.

Exempel med felidentifiering

I följande exempel beräknar exempelkoden det nya underordnade EmployeeId värdet och identifierar sedan eventuella överträdelser för nyckeln och återgår till INS_EMP markören för att beräkna EmployeeId värdet för den nya raden.

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

Exempel med en serialiserbar transaktion

Indexet Org_BreadthFirst säkerställer att en intervallsökning används för att @last_child bestämma. Förutom andra felfall som ett program kanske vill kontrollera, anger en duplicerad nyckelöverträdelse efter infogningen ett försök att lägga till flera anställda med samma ID och måste därför @last_child omberäknas. Följande kod beräknar det nya nodvärdet i en serialiserbar transaktion:

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;

Följande kod fyller tabellen med tre rader och returnerar resultatet:

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

EXECUTE AddEmp 0x, 'Sariya';
GO

EXECUTE AddEmp 0x58, 'Mary';
GO

SELECT * FROM Org_T2

Här är resultatet.

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

Framtvinga ett träd

Föregående exempel illustrerar hur ett program kan se till att ett träd underhålls. För att upprätthålla ett träd med hjälp av begränsningar kan en beräknad kolumn som definierar föräldern för varje nod skapas med en främmande nyckelbegränsning tillbaka till primärnyckelns ID.

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

Den här metoden för att framtvinga en relation är att föredra när kod som inte är betrodd för att underhålla det hierarkiska trädet har direkt DML-åtkomst till tabellen. Den här metoden kan dock minska prestandan eftersom begränsningen måste kontrolleras för varje DML-åtgärd.

Hitta förfäder genom att använda CLR

En vanlig åtgärd som involverar två noder i en hierarki är att hitta den lägsta gemensamma förfadern. Den här uppgiften kan skrivas i antingen Transact-SQL eller CLR, eftersom typen hierarchyid är tillgänglig i båda. CLR rekommenderas eftersom prestandan är snabbare.

Använd följande CLR-kod för att lista förfäder och för att hitta den lägsta gemensamma förfader.

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

Om du vill använda ListAncestor metoderna och CommonAncestor i följande Transact-SQL exempel skapar du DLL och skapar HierarchyId_Operations sammansättningen i SQL Server genom att köra kod som liknar följande exempel:

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

Lista över överordnade

Att skapa en lista över överordnade noder är en vanlig åtgärd, till exempel för att visa position i en organisation. Ett sätt att göra detta är att använda en tabellvärdesfunktion med hjälp av klassen HierarchyId_Operations som definierades tidigare:

Använda Transact-SQL:

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

Exempel på användning:

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

Hitta den lägsta gemensamma överordnade

Använd den HierarchyId_Operations klass som definierades tidigare och skapa följande Transact-SQL-funktion för att hitta den lägsta gemensamma förfader för två noder i en hierarki.

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