• Статья

Использование типов данных hierarchyid (компонент Database Engine)

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

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

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

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

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

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

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

Тип данных hierarchyid, появившийся в продукте SQL Server 2008, предназначен для хранения и обработки иерархических данных. Тип hierarchyid оптимизирован для представления деревьев — самого распространенного типа иерархических данных.

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

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

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

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

  • Сравнение проводится в порядке приоритета глубины

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

  • Поддержка произвольных вставок и удалений

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

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

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

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

  • Параллельными процессами создания и присвоения значений hierarchyid управляет само приложение. Нет никакой гарантии, что значения hierarchyid уникальны, если приложение не использует ограничение уникального ключа или не обеспечивает уникальность своей логикой.

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

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

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

  • В глубину

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

Узлы хранятся вместе.

  • В ширину

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

Объекты каждого уровня иерархии хранятся вместе.

Примеры

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

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

В индексе преимущественно в ширину все прямые потомки узла хранятся в одном месте. Поэтому индекс преимущественно в ширину эффективен для запросов по прямым потомкам. Например: «найти всех прямых подчиненных этого начальника».

Выбор стратегии индексирования (в глубину, в ширину или обе) и ключа кластеризации зависит от того, какие из вышеуказанных типов запросов обрабатываются чаще и какие операции более важны (SELECT или DML). Пример использования стратегий индексирования см. в разделе Учебник. Использование типа данных hierarchyid.

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

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

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

  • XML

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

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

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

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

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

В настоящее время большинство деревьев представлены методом «родители-потомки». Для перехода со структуры «родители-потомки» на тип hierarchyid проще всего создать временный столбец или временную таблицу для хранения количества узлов на каждом уровне иерархии. Пример преобразования таблицы с организацией «родители-потомки» см. в разделе Учебник. Использование типа данных hierarchyid (урок 1).

Преобразование запросов для типа hierarchyid.

Для максимальной скорости обработки запросов иерархических данных приложение SQL Server автоматически выполняет 3 вида преобразования запросов с использованием типа hierarchyid. Результаты этих преобразований отображаются в выходных данных инструкции showplan для преобразованных запросов.

Функция GetAncestor преобразуется в просмотр диапазона по индексу и остаточный предикат

Функция GetAncestor(n) возвращает n-го предка узла. Это удобно, если требуется точная связь между двумя узлами (родитель, потомок и т. п.), в отличие от более общей функции IsDescendantOf.

Например, следующий запрос возвращает список всех сотрудников, непосредственно подчиняющихся руководителю @value:

DECLARE @value hierarchyid ;
SELECT * FROM AdventureWorks2008R2.HumanResources.Employee 
WHERE  OrganizationNode.IsDescendantOf(@value) = 1;