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

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

  • Статья

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

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

  • Организационная структура

  • Файловая система

  • группа задач в проекте;

  • Классификация языковых терминов

  • Диаграмма связей между веб-страницами

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

В этом разделе

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

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

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

  • Ниже описаны подходы к индексированию иерархических данных:

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

    • Переход со структуры «родители-потомки» на тип hierarchyid

    • Управление древовидной структурой с помощью hierarchyid

    • Принудительное формирование древовидной структуры

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

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

    • Нахождение ближайшего общего предка

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

Основные свойства типа 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 управляет само приложение. Нет никакой гарантии, что значения hierarchyid уникальны, если приложение не использует ограничение уникального ключа или не обеспечивает уникальность своей логикой.

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

[В начало]

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

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

  • Родители-потомки

  • XML

Использование типа hierarchyid дает больше возможностей. Однако есть ситуации (см. ниже), когда другие методы более эффективны.

Родители-потомки

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

USE AdventureWorks2012 ;
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, изменение местоположения строки влияет на 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). Пример использования стратегий индексирования см. в разделе Учебник. Использование типа данных hierarchyid.

[В начало]

Примеры

Для организации данных в ширину можно использовать метод GetLevel(). В следующем примере создаются оба типа индекса: преимущественно в глубину и преимущественно в ширину.

USE AdventureWorks2012 ; 
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

[В начало]

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

Переход со структуры «родители-потомки» на тип 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 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 

UPDATE Org_T2 
SET @last_child = LastChild = EmployeeId.GetDescendant(LastChild,NULL)
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;
using Microsoft.SqlServer.Types;

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.IsDescendant(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

Пример использования:

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

[В начало]

См. также

Справочник

hierarchyid (Transact-SQL)

Основные понятия

Справочник по методам типа данных hierarchyid

Учебник. Использование типа данных hierarchyid