共用方式為


階層式資料 (SQL Server)

適用於:SQL Server Azure SQL 資料庫 Azure SQL 受控執行個體

內建 hierarchyid 資料類型讓儲存與查詢階層式資料更容易。 hierarchyid 最適合表示樹狀目錄,這是階層式資料最常見的類型。

階層式資料的定義為一組資料項目,這些資料項目會依據階層式關聯性,彼此相關。 階層式關聯性表示資料的一個項目是另一個項目的父代。 通常儲存在資料庫的階層式資料範例包含下列項目:

  • 組織結構
  • 檔案系統
  • 專案中的一組工作
  • 語言詞彙的分類表
  • 網頁之間的連結圖形

使用 hierarchyid 做為資料類型來建立具有階層式結構的資料表,或描述儲存在另一個位置的階層式資料結構。 使用 Transact-SQL 中的 hierarchyid 函數來查詢及管理階層式資料。

索引鍵屬性

hierarchyid 資料類型的值代表樹狀目錄階層中的位置。 hierarchyid 的值具有下列屬性:

  • 極度壓縮

    代表樹狀目錄 (含有 n 個節點) 中之節點所需的平均位元數目會因平均扇出 (節點子系的平均數目) 而不同。 若為小型 fanout (0-7),其大小約為 $6log{A}{n}$ 個位元,其中 A 是平均 fanout。 在平均 fanout 為六個階層之 100,000 人員的組織階層中,節點會佔用大約 38 位元。 然後,這會四捨五入成 40 位元 (或 5 個位元組),以便進行儲存。

  • 比較是按照深度優先順序

    假設有兩個 hierarchyid 值 (ab),a < b 表示在樹狀目錄的深度優先周遊中,ab 前面。 hierarchyid 資料類型的索引採用深度優先順序,而且在深度優先周遊中彼此接近的節點會以彼此接近的方式儲存。 例如,某筆記錄的子系會儲存在該記錄旁。

  • 支援任意插入和刪除

    透過使用 GetDescendant (資料庫引擎) 方法,您就一定能夠在任何指定節點的右側、任何指定節點的左側,或任何兩個同層級之間產生同層級。 在階層中插入或刪除任意的節點數目時,比較屬性會保留下來。 大部分的插入和刪除項目都會保留壓縮度屬性。 不過,兩個節點之間的插入項目則會以稍微少的壓縮表示來產生 hierarchyid 值。

限制

hierarchyid 資料類型具有下列限制:

  • hierarchyid 類型的資料行不會自動代表樹狀目錄。 應用程式負責決定是否要產生並指派 hierarchyid 值,以便讓資料列之間所需的關聯性反映在值中。 有些應用程式可能有 hierarchyid 類型的資料行,表示在另一個資料表中定義之階層的位置。

  • 應用程式負責管理產生與指派 hierarchyid 值的並行。 除非應用程式使用唯一索引鍵條件約束或透過自己的邏輯強制本身的唯一性,否則,不保證資料行中的 hierarchyid 值是唯一的。

  • hierarchyid 值代表的階層式關聯性不會像外部索引鍵關聯性般強制執行。 如果 A 擁有子系 B,然後刪除 A 留下 B,讓關聯性變成不存在的記錄,這種階層式關聯性是可能發生而且有時候是恰當的。 如果無法接受這種行為,應用程式必須在刪除父系前,查詢下階。

使用 hierarchyid 替代選項的時機

代表階層式資料的兩個 hierarchyid 替代選項為:

  • 父子式
  • XML

hierarchyid 通常優先於這些替代選項。 但是,在本文中詳細介紹的特定情況下,替代方案可能更佳。

父子式

使用父子式方式時,每個資料列都包含一個父系的參考。 下表定義在父子關聯性中包含父系和子系資料列時所使用的一般資料表:

USE AdventureWorks2022;
GO

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

比較父子式和 hierarchyid 的一般作業:

  • 使用 hierarchyid 進行子樹查詢時,速度明顯加快。
  • 而使用 hierarchyid 進行直接下階查詢時,速度則稍慢。
  • 使用 hierarchyid 移動非分葉節點時,速度比較慢。
  • 使用 hierarchyid 插入非分葉節點與插入或移動分葉節點時,其複雜程度相同。

下列狀況存在時,最好使用父子式:

  • 索引鍵的大小很重要。 如果節點數目相同, hierarchyid 值會等於或大於整數系列 (smallintintbigint) 值。 在極少的情況下,這是使用 [父子式] 的唯一原因,因為比起使用 [父子式] 結構時所需要的通用資料表運算式, hierarchyid 的 I/O 位置明顯較好,而且 CPU 的複雜性較高。

  • 查詢很少會查詢整個階層的區段。 換句話說,查詢通常只處理階層中的單一點。 在這些案例中,共同位置並不重要。 例如,如果組織資料表僅用於處理個別員工的薪資,最好使用 [父子式]。

  • 非分葉的子樹會經常移動,因此效能非常重要。 在父子式表示中,變更資料列在階層中的位置會影響單一資料列。 在 hierarchyid 使用方式中變更資料列的位置會影響 n 個資料列,其中 n 是要移動之樹狀子目錄中的節點數目。

    如果非分葉子樹經常移動且效能非常重要,但是大部分的移動都是在定義良好的階層層級進行時,請考慮將較高和較低的層級分割為兩個階層。 這樣會全部移到較高階層的分葉層級中。 例如,請考慮由服務主控之網站的階層。 網站包含許多以階層方式排列的頁面。 主控的網站可能會移到網站階層的其他位置,但是從屬的頁面很少會重新排列。 這可能會透過下列方式表示:

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

XML

XML 文件是一個樹狀結構,因此,單一的 XML 資料類型執行個體可以代表一個完整的階層。 在 SQL Server 中建立 XML 索引時,hierarchyid 值會用在內部,以表示在階層中的位置。

如果以下所有狀況成立,使用 XML 資料類型可能比較好:

  • 永遠會儲存與擷取完整的階層。
  • 應用程式使用的資料為 XML 格式。
  • 述詞搜尋會受到相當的限制,而且效能並不重要。

例如,如果應用程式追蹤多個組織,務必儲存與擷取完整的組織階層,而且不要在單一組織中查詢,下列表單的資料表才可能有意義:

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

階層式資料的索引策略

編製階層式資料索引有兩種策略:

  • 深度優先

    如果是深度優先的索引,會將子樹中的資料列儲存在彼此的附近。 例如,透過某位經理管理的所有員工都會儲存在經理記錄的附近。

    在深度優先的索引中,節點子樹的所有節點都會位於相同位置。 因此,深度優先的索引在回應關於子樹的查詢 (例如,「尋找此資料夾及其子資料夾中的所有檔案」) 時很有效率

  • 廣度優先

    廣度優先索引會將資料列與階層的每個層級儲存在一起。 例如,直接由相同經理管理之員工的記錄會儲存在彼此的附近。

    在廣度優先的索引中,節點的所有直接子系都會位於相同位置。 因此,廣度優先的索引在回應關於下層子系的查詢 (例如,「尋找直接回報給此經理的所有員工」) 時很有效率

不論是讓深度優先、廣度優先,或是兩者,還是那個要產生叢集索引鍵 (如果有的話),都取決於上述查詢類型的相對重要性,以及 SELECT 和 DML 作業的相對重要性。 如需索引策略的詳細範例,請參閱< Tutorial: Using the hierarchyid Data Type>。

建立索引

GetLevel() 方法可以用來建立廣度優先排序。 在下列範例中,會同時建立廣度優先和深度優先的索引:

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

範例

本文 Transact-SQL 程式碼範例使用 AdventureWorks2022AdventureWorksDW2022 範例資料庫,從 Microsoft SQL Server Samples 和 Community Projects (Microsoft SQL Server 範例和社群專案)首頁即可下載。

基本範例

下列範例有意經過簡化以協助您開始使用。 首先,建立資料表以保留一些地理資料。

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

現在,插入一些大陸、國家/地區、州和城市的資料。

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

選取資料,並加入資料行以將層級資料轉換為容易了解的文字值。 此查詢也會依 hierarchyid 資料類型來排序結果。

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

以下為結果集。

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

即使階層內部不一致,仍具有有效的結構。 Bahia 是唯一的州。 它會在階層中以 Brasilia 城市的同層級顯示。 同樣地,McMurdo Station 沒有父國家/地區。 使用者必須決定此階層類型是否適用。

加入另一個資料列並選取結果。

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

這會顯示更多可能的問題。 Kyoto 可插入為層級 /1/3/1/,但卻沒有父層級 /1/3/。 而 London 和 Kyoto 的 hierarchyid 值相同。 同樣地,使用者必須決定此階層類型是否適用,並封鎖不適用的值。

此外,此資料表未使用階層 '/' 的頂端。 由於所有大陸沒有共同的父系,因此已省略。 您可以加入整個地球,以加入一個父系。

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

從父子式移轉到 hierarchyid

大部分的樹狀目錄都是使用 [父子式] 結構。 從 [父子式] 結構遷移到使用 hierarchyid 的資料表最簡單的方式,就是使用暫存資料行或暫存資料表來追蹤每個階層層級的節點數。 如需遷移 [父子式] 資料表的範例,請參閱 教學課程:使用 hierarchyid 資料類型 的第 1 課。

使用 hierarchyid 管理樹狀結構

雖然 hierarchyid 資料行不需要代表樹狀結構,但是應用程式可以輕易地確認這就是樹狀結構。

  • 產生新值時,請執行下列其中一個步驟:

    • 追蹤父資料列中的最後一個子系號碼。
    • 計算最後一個子系。 若要有效率地執行這個動作,需要使用廣度優先索引。
  • 在資料行上建立唯一的索引 (也許是叢集索引鍵的一部份) 以強制執行唯一性。 若要確保插入唯一的值,請執行下列其中一個步驟:

    • 偵測唯一的索引鍵違規失敗,然後重試。
    • 判斷每個新子節點的唯一性,然後插入該子節點做為可序列化交易的一部分。

使用錯誤偵測的範例

在下列範例中,範例程式碼會計算新子系的 EmployeeId 值,然後偵測任何索引鍵違規,並傳回 INS_EMP 標記,以便為新的資料列重新計算 EmployeeId 值:

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

使用序列化交易的範例

索引 Org_BreadthFirst 可確保判斷 @last_child 會使用範圍搜尋。 除了應用程式可能想要檢查的其他錯誤情況之外,插入後的重複索引鍵違規會指出使用相同識別碼新增多個員工的嘗試,因此必須重新計算 @last_child。 下列程式碼會在可序列化的交易內計算新節點值:

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;

下列程式碼會使用三個資料列擴展資料表,然後傳回結果:

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

AddEmp 0x, 'Sariya'
GO

AddEmp 0x58, 'Mary'
GO

SELECT * FROM Org_T2

以下為結果集。

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

強制執行樹狀結構

上述範例說明應用程式可以如何確保樹狀結構的維護。 若要透過條件約束強制執行樹狀結構,可以使用傳回主要索引鍵識別碼的外部索引鍵條件約束建立定義每個節點之父系的計算資料行。

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

不信任可以維護階層式樹狀結構的程式碼具有資料表的 DML 直接存取權時,最好使用這個方法強制關聯性。 不過,由於必須針對每個 DML 作業檢查條件約束,這個方法可能會降低效能。

透過使用 CLR 尋找上階

與階層中兩個節點相關的常見作業就是尋找最低通用上階。 此任務可寫入 Transact-SQL 或 CLR 中,因為這兩者都可以使用 hierarchyid 類型。 因為效能會更快,因此建議使用 CLR。

使用下列的 CLR 程式碼,列出上階並尋找最低通用上階:

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

若要在下列 Transact-SQL 範例中使用 ListAncestorCommonAncestor 方法,請執行類似如下範例的程式碼,在 SQL Server 中建置 DLL 並建立 HierarchyId_Operations 組件:

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

列出上階

建立節點上階清單是一個常見的作業,例如,在組織中顯示位置。 其中一個方法是,利用前面定義的 HierarchyId_Operations 類別,使用資料表值函數:

使用 Transact-SQL:

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

使用範例:

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

尋找最低通用上階

使用前面定義的 HierarchyId_Operations 類別建立下列的 Transact-SQL 函數,尋找與階層中包含兩個節點的最低通用上階:

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

使用範例:

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

產生的節點是 /1/1/

移動樹狀子目錄

另一個常見的作業是移動子樹。 以下程序使用 @oldMgr 的樹狀子目錄,並讓其 (包括 @oldMgr) 成為 @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