Иерархические данные (SQL Server)

Статья
07/30/2024

Область применения: SQL Server База данных SQL Azure Управляемый экземпляр SQL Azure

Встроенный тип данных hierarchyid упрощает хранение и запрос иерархических данных. hierarchyid оптимизирован для представления деревьев, которые являются наиболее распространенным типом иерархических данных.

Иерархические данные представляют собой набор элементов данных, связанных между собой иерархическими связями. Иерархические связи — это связи, в которых один из элементов данных является родителем другого элемента. Примеры иерархических данных, которые обычно хранятся в базах данных, включают следующие элементы:

Организационная структура
Файловая система
группа задач в проекте;
Классификация языковых терминов
Диаграмма связей между веб-страницами

Тип данных hierarchyid используется для создания таблиц с иерархической структурой или для описания иерархической структуры данных, которые хранятся в другом расположении. Используйте функции hierarchyid в Transact-SQL для запроса иерархических данных и управления ими.

Ключевые свойства

Значение типа данных hierarchyid представляет позицию в древовидной иерархии. Значения hierarchyid обладают следующими свойствами.

Исключительная компактность

Среднее число бит, необходимое для представления узла в древовидной структуре с n узлами, зависит от среднего количества потомков у узла. Для небольших вентиляторов (0-7), размер составляет около $6log{A}{n}$ битов, где A является средним вентилятором. Узел в организационной иерархии 100 000 человек со средним вентилятором шести уровней занимает около 38 бит. Эта величина округляется до 40 бит (5 байт), которые необходимы для хранения.
Сравнение проводится в порядке приоритета глубины

Учитывая два значения a иерархии и a < b b, означает, что a перед b глубиной первого обхода дерева. Индексы для типов данных hierarchyid располагаются в порядке приоритета глубины, а узлы, встречающиеся рядом при проходе по дереву с приоритетным направлением глубины, хранятся рядом друг с другом. Например, дочерние элементы записи хранятся рядом с этой записью.
Поддержка произвольных вставок и удалений

С помощью метода GetDescendant (ядро СУБД) всегда можно создать одноуровневый элемент справа от любого заданного узла, слева от любого заданного узла или между двумя братьями и сестрами. Свойство сравнения сохраняется, если произвольное число узлов вставляется в иерархию или удаляется из нее. Большинство операций вставки и удаления сохраняют свойство компактности. Однако вставки между двумя узлами создают значения иерархии с немного менее компактным представлением.

Ограничения

Тип данных 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 занимает столько же или больше памяти, чем значение одного из целочисленных типов (smallint, int, bigint). Это лишь причина использования родительского или дочернего элемента в редких случаях, так как иерархия имеет значительно лучшую локализацию операций ввода-вывода и ЦП, чем распространенные выражения таблицы, необходимые при использовании родительской или дочерней структуры.
Запросы редко бывают обращены сразу к нескольким частям иерархии. Иными словами, запрос обычно касается только одной точки иерархической структуры. В таких случаях совместное размещение не важно. Например, родитель или ребенок выше, если таблица организации используется только для обработки заработной платы для отдельных сотрудников.
Нелесовые поддеревы часто перемещаются и производительность очень важна. В родительском или дочернем представлении изменение расположения строки в иерархии влияет на одну строку. Изменение расположения строки в использовании hierarchyid влияет на строки n , где n — количество узлов в перемещаемом поддереве.

Если нелесовые поддеревы часто перемещаются и производительность важны, но большинство перемещения находятся на четко определенном уровне иерархии, рассмотрите возможность разделения более высоких и более низких уровней на две иерархии. В этом случае все перемещения будут происходить на последнем уровне верхней иерархии. Например, рассмотрим иерархию веб-сайтов, входящих в одну службу. Сайты содержат много страниц, имеющих иерархическую структуру. Размещенные сайты могут быть перемещены в другие расположения в иерархии сайтов, но подчиненные страницы редко переупорядочены. Это можно представить так:
```
CREATE TABLE HostedSites (
    SiteId HIERARCHYID,
    PageId HIERARCHYID
);
GO
```

XML

XML-документ является деревом, поэтому один экземпляр типа данных XML может представлять всю структуру. В SQL Server при создании XML-индекса значения иерархии используются внутренне для представления позиции в иерархии.

Использование типа данных 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 в этой статье используют AdventureWorks2022 базу данных или AdventureWorksDW2022 пример базы данных, которую можно скачать с домашней страницы примеров и проектов сообщества 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

Иерархия имеет допустимую структуру, несмотря на то, что она не является внутренне согласованной. Байя — единственный штат. Он отображается в иерархии как одноранговый по отношению к городу Бразилиа. Аналогичным образом, станция McMurdo не имеет родительской страны или региона. Необходимо решить, подходит ли этот тип иерархии для использования.

Добавьте еще одну строку и выберите результаты.

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

Это демонстрирует наличие других возможных проблем. Киото можно вставить как уровень /1/3/1/ , несмотря на отсутствие родительского уровня /1/3/. И Лондон и Киото имеют одинаковое значение свойства hierarchyid. Опять-таки пользователи должны решить, подходит ли этот тип иерархии для использования, и заблокировать значения, недопустимые для использования.

Кроме того, эта таблица не использовала верхнюю часть иерархии '/'. Это было опущено, потому что нет общего родителя всех континентов. Его можно добавить путем добавления всей планеты.

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

Миграция из родительского или дочернего в иерархию

Большинство деревьев представлены с помощью родительского или дочернего. Самый простой способ миграции из родительской или дочерней структуры в таблицу с помощью hierarchyid — использовать временный столбец или временную таблицу для отслеживания количества узлов на каждом уровне иерархии. Пример переноса родительской или дочерней таблицы см. в уроке 1 руководства. Использование типа данных hierarchyid.

Управление деревом с помощью 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;
    }
}

Чтобы использовать ListAncestor методы и CommonAncestor методы в следующих примерах Transact-SQL, создайте библиотеку DLL и создайте сборку HierarchyId_Operations в SQL Server, выполнив следующий пример:

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

Поделиться через

Иерархические данные (SQL Server)

Ключевые свойства

Ограничения

Когда следует использовать альтернативные варианты для hierarchyid

Родительский или дочерний

XML

Стратегии индексирования иерархических данных

Создать индексы

Примеры

Простой пример

Миграция из родительского или дочернего в иерархию

Управление деревом с помощью hierarchyid

Пример использования обнаружения ошибок

Пример использования сериализуемой транзакции

Принудительное применение дерева

Поиск предков с помощью среды CLR

Перечисление предков

Поиск самого низкого общего предка

Перемещение поддерев

Обратная связь

Дополнительные ресурсы

Поделиться через

Иерархические данные (SQL Server)

Ключевые свойства

Ограничения

Когда следует использовать альтернативные варианты для hierarchyid

Родительский или дочерний

XML

Стратегии индексирования иерархических данных

Создать индексы

Примеры

Простой пример

Связанные задачи

Миграция из родительского или дочернего в иерархию

Управление деревом с помощью hierarchyid

Пример использования обнаружения ошибок

Пример использования сериализуемой транзакции

Принудительное применение дерева

Поиск предков с помощью среды CLR

Перечисление предков

Поиск самого низкого общего предка

Перемещение поддерев

Связанный контент

Обратная связь

Дополнительные ресурсы