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

Статья
05/23/2023

Применяется к:SQL Server Azure SQL Database Azure, управляемому экземпляру SQL Azure

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

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

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

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

Основные свойства типа hierarchyid

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

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

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

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

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

Ограничения типа данных hierarchyid

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

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

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

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

Примеры

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

Следующий пример намеренно упрощен, чтобы легче было приступить к работе. Сначала создайте таблицу для хранения определенных географических данных.

CREATE TABLE SimpleDemo  
(
    Level hierarchyid NOT NULL,  
    Location nvarchar(30) NOT NULL,  
    LocationType nvarchar(9) NULL
);

Теперь вставьте данные для некоторых континентов, стран или регионов, штатов и городов.

INSERT SimpleDemo  
    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 SimpleDemo 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

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

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

INSERT SimpleDemo  
    VALUES ('/1/3/1/', 'Kyoto', 'City'), ('/1/3/1/', 'London', 'City');  
SELECT CAST(Level AS nvarchar(100)) AS [Converted Level], * FROM SimpleDemo ORDER BY Level;

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

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

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

Чтобы использовать методы 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  
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