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

Применимо к:SQL Server Azure SQL База данных Azure SQL Управляемый экземпляр SQL База данных в Microsoft Fabric

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

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

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

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

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

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

Чрезвычайно компактный

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

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

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

Limitations

Тип данных hierarchyid имеет следующие ограничения.

Столбец типа hierarchyid не представляет собой дерево автоматически. Приложение должно создавать и назначать значения иерархии таким образом, чтобы требуемое отношение между строками отражается в значениях. Некоторые приложения могут содержать столбец типа hierarchyid , указывающий местоположение в иерархии, определенной в другой таблице.
Приложение само должно управлять параллелизмом при создании и назначении значений hierarchyid. Нет никаких гарантий, что значения иерархии в столбце уникальны, если приложение не использует уникальное ограничение ключа или применяет уникальность через собственную логику.
Иерархические связи, представленные значениями hierarchyid, не обеспечиваются так же, как связь по внешнему ключу. Возможно, а иногда и уместно, наличие иерархической связи, при которой у A есть дочерний элемент B, а затем A удаляется, в результате чего у B остаётся связь с несуществующей записью. Если это неприемлемо, приложение должно запросить потомков, прежде чем удалять родителей.

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

Кроме типа hierarchyid , есть еще два способа представления иерархических данных:

Parent/child
XML

hierarchyid обычно превосходит эти альтернативы. Однако существуют конкретные ситуации, подробно описанные в этой статье, где альтернативные варианты, скорее всего, выше.

Parent/child

При использовании подхода "родительский/дочерний" каждая строка содержит ссылку на родительский элемент. В следующей таблице определяется типичная таблица, содержащая родительские и дочерние строки в связи «родитель-потомок»:

USE AdventureWorks2022;
GO

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

Сравнение моделей parent/child и hierarchyid для типичных операций:

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

Отношение «родительский/дочерний» может быть предпочтительнее при следующих условиях:

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

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

Есть два подхода к индексированию иерархических данных:

Depth-first

Индекс с обходом в глубину хранит строки поддерева рядом друг с другом. Например, записи всех сотрудников, которые подчиняются руководителю, хранятся рядом с записью их руководителя.

В индексе с обходом в глубину все узлы в поддереве узла расположены рядом. Поэтому индексы глубины эффективны для ответа на запросы о поддереве, например "Поиск всех файлов в этой папке и ее вложенных папок".
Breadth-first

Если используется индексирование в ширину, строки одного уровня иерархии хранятся вместе. Например, записи всех сотрудников, напрямую подчиненных одному и тому же руководителю, хранятся рядом друг с другом.

В индексе с обходом в ширину все прямые дочерние элементы узла расположены вместе. В первую очередь индексы являются эффективными для ответа на запросы о непосредственных дочерних элементах, таких как "Поиск всех сотрудников, которые сообщают непосредственно этому руководителю".

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

Examples

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

Большинство деревьев представлены с помощью родительского или дочернего. Самый простой способ миграции из родительской или дочерней структуры в таблицу с помощью 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

EXECUTE AddEmp 0x, 'Sariya';
GO

EXECUTE 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 FOREIGN KEY 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 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

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

Используя класс HierarchyId_Operations, определённый ранее, создайте следующую функцию Transact-SQL для поиска ближайшего общего предка для двух узлов в иерархии:

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