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

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

Однако, разработчики СУБД MS SQL предлагают в своей новой версии MS SQL 2008 для реализации древовидной иерархии новый тип хранения данных hierarchyid.

Введение

Тип hierarchyid — это системный тип базы данных, размер которого может меняться в зависимости от структуры дерева (его глубины) и среднего числа потомков узлов. В MSDN приводятся следующие расчеты: для дерева с иерархией в 6 уровней для 100000 человек hierarchyid займет 38 бит, которые БД округлит до 40 бит или 5 байт. Максимальный же размер, который может занимать hierarchyid равен 892 байта.

Создание таблицы

Для начала создадим весьма простую таблицу, которая будет хранить в себе иерархию персонала в некой компании:

CREATE TABLE Table_1(
hid hierarchyid NOT NULL,
userId int NOT NULL,
userName nvarchar(50) NOT NULL,
CONSTRAINT PK_Table_1 PRIMARY KEY CLUSTERED
(
[hid] ASC
))

В таблице будет хранится: hierarchyid, id служащего и его имя. Далее мы попробуем воссоздать в этой таблице следующую иерархию персонала:

1 Иванов

    2 Петров

        7 Смирнов

            8 Пупкин

    3 Сидоров

    4 Васечкин

        5 Круглов

        6 Квадратов

Создание иерархии

Первым делом создадим корень иеррахии:

insert into Table_1
values(hierarchyid::GetRoot(), 1, ‘Иванов’)

Обратите внимание на hierarchyid::GetRoot() — это статический метод, который всегда возвращает идентификатор корня иерархии.

Далее, добавим к корневой записи потомков:

declare @Id hierarchyid

select @Id = MAX(hid)
from Table_1
where hid.GetAncestor(1) = hierarchyid::GetRoot()

insert into Table_1
values(hierarchyid::GetRoot().GetDescendant(@id, null), 2, ‘Петров’);

select @Id = MAX(hid)
from Table_1
where hid.GetAncestor(1) = hierarchyid::GetRoot()

insert into Table_1
values(hierarchyid::GetRoot().GetDescendant(@id, null), 3, ‘Сидоров’);

select @Id = MAX(hid)
from Table_1
where hid.GetAncestor(1) = hierarchyid::GetRoot()

insert into Table_1
values(hierarchyid::GetRoot().GetDescendant(@id, null), 4, ‘Васечкин’);

В этом коде примечательными являются следующие участки кода:

• hid.GetAncestor(1) = hierarchyid::GetRoot() — выбирает все записи, предком (прямым) которых является корень;
• hierarchyid::GetRoot().GetDescendant(@id, null) — выбирает первый свободный hierarchyid прямых потомков корня дерева. Описание параметров я приведу ниже.

Завершим картину, заполнив таблицу всеми оставшимися записями:

declare @phId hierarchyid
select @phId = (SELECT hid FROM Table_1 WHERE userId = 2);

select @Id = MAX(hid)
from Table_1
where hid.GetAncestor(1) = @phId

insert into Table_1
values(@phId.GetDescendant(@id, null), 7, ‘Смирнов’);

select @phId = (SELECT hid FROM Table_1 WHERE userId = 4);

select @Id = MAX(hid)
from Table_1
where hid.GetAncestor(1) = @phId

insert into Table_1
values(@phId.GetDescendant(@id, null), 5, ‘Круглов’);

select @Id = MAX(hid)
from Table_1
where hid.GetAncestor(1) = @phId

insert into Table_1
values(@phId.GetDescendant(@id, null), 6, ‘Квадратов’);

select @phId = (SELECT hid FROM Table_1 WHERE userId = 7);

select @Id = MAX(hid)
from Table_1
where hid.GetAncestor(1) = @phId

insert into Table_1
values(@phId.GetDescendant(@id, null), 8, ‘Пупкин’);

Обратите внимание, что весь приведенный в статье код следует выполнять одним скриптом

После того, как мы выполним весь этот код мы получим следующую картину

select hid.ToString(), hid.GetLevel(), * from Table_1

/               0   0x                    1  Иванов

/1/             1   0x58                  2  Петров

/1/1/           2   0x5AC0                7  Смирнов

/1/1/1/         3   0x5AD6                8  Пупкин

/2/             1   0x68                  3  Сидоров

/3/             1   0x78                  4  Васечкин

/3/1/           2   0x7AC0                5  Круглов

/3/2/           2   0x7B40                6  Квадратов

WIN-Z6U4ALRNDSU(WIN-Z6U4ALRNDSU\Administrator): (8 row(s) affected)

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

Вспомогательные функции

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

• GetAncestor — выдает hierarchyid предка, можно указать уровень предка, например 1 выберет непосредственного предка;
• GetDescendant — выдает hierarchyid потомка, принимает два параметра, с помощью которых можно управлять тем, какого именно потомка необходимо получить на выходе;
• GetLevel — выдает уровень hierarchyid;
• GetRoot — выдает уровень корня;
• IsDescendant — проверяет является ли hierarchyid переданный через параметр потомком;
• Parse — конвертирует строковое представление hierarchyid в собственно hierarchyid;
• Reparent — позволяет изменить текущего предка;
• ToString — конвертирует hierarchyid в строковое представление.

Заключение

MS SQL 2008 предлагает новый способ хранения данных, которые представляют собой какую-либо древовидную иерархию. Для этих целей вводится тип hierarchyid, который содержит в себе «путь» к элементу иерархии. Для помощи программисту баз данных предлагается набор вспомогательных функции, которые позволяют организовать представление иерархии, перемещение данных, доступ к элементам и добавление новых элементов иерархии.

Предложенный вариант, на мой взгляд, является отличной заменой стандартного способа хранения иерархических данных через поле parentId (предок). Использование hierarchyid позволяет создавать иерархические структуры с написанием минимумом кода.

(c) xaoccps

Физический формат хранения значений этого типа.

Единственная тема заслуживающая, на мой взгляд, внимания, которая осталась нетронутой – это физический формат хранения значений этого типа. Почему это важно? Потому, что в отличие от простого идентификатора, HierarchyId значения содержат список номеров всех узлов, которые нужно пройти, от корня иерархии до заданного узла. А каждый номер узла может состоять из нескольких компонентов (чисел). То есть для больших иерархий, HierarchyId значения могут быть достаточно длинными (принятое в SQL Server 2008 ограничение — 892 байт). Учитывая, что по этим значениям наверняка будут строиться индексы и выполняться многочисленных выборки, то чем они будут компактнее, тем лучше.

Напомню, что в логической (текстовой) форме HierarchyId значения представляют собой список номеров всех узлов по пути от корня иерархии до некоторого заданного узла разделенный символом «/». Каждый номер узла состоит из одного или нескольких компонентов (чисел) разделенных символом «.» (точка). Пример корректных HierarchyId значений:

• /
• /1/
• /0.3.-7/
• /1/3/
• /0.1/0.2/

Физическая кодировка HierarchyId значений, очевидно, должна удовлетворять следующим требованиям:

• Должна быть как можно более компактной
• Должна обеспечивать “правильный” порядок сортировки HierarchyId значений (то есть, например, значение /0.1/0.2/ должно быть больше чем значение /0.1/0/).

В SQL Server 2008 HierarchyId значения кодируются используя следующую схему:

<Компонент номера узла 1><Битовый флаг перехода на следующий уровень 1>
<Компонент номера узла 2><Битовый флаг перехода на следующий уровень 2>
…
<Компонент номера узла N><Битовый флаг перехода на следующий уровень N>

То есть, например, значение /7/4.5/ кодируется согласно этой схеме так:

<7> /* Компонент номера узла */ <1> /* переход на следующий уровень */
<4> /* Компонент номера узла */ <0> /* нет перехода на следующий уровень */
<5> /* Компонент номера узла */ <1>  /* переход на следующий уровень */

Пока все достаточно очевидно. Самое интересное – это способ кодирования компонентов номеров узлов. Для этого в SQL Server 2008 применен подход, похожий на тот, который используют архиваторы при сжатии данных. Отдельные компоненты номеров узлов кодируются битовыми последовательностями разной длины. Более вероятным значениям соответствуют более короткие битовые последовательности, а менее вероятным – более длинные последовательности.

Каждый компонент номера узла состоит из двух частей – кода диапазона и собственно значения. В таблице 1 представлены все используемые SQL сервером диапазоны. Например, если требуется закодировать значение  11, то согласно таблице, будет использован диапазон 8–15 и соответственно двоичное представление этого компонента будет равно:

101 /* код диапазона 8-15 */
011 /* значение пересчитанное на начало диапазона (11 – 8 = 3) */

Таблица 1

Согласно электронной документации по SQL Server 2008 (BOL), среднее количество бит требуемых для представления узла в иерархии с N узлами и небольшим (в диапазоне 0-7) средним количеством дочерних узлов A (fanout), будет равно 6*log_AN. То есть для иерархии из 100,000 элементов и средним количеством дочерних узлов равным 6, для кода узла потребуется примерно 38 бит или после округления 5 байт.

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

Давайте вспомним про требование ”правильной” сортировки HierarchyId значений. Согласно этому требованию, например, значение /1/ должно быть меньше значения /1.1/. Но если закодировать эти значения так:

/1/        <1> /* номер */ <1> /* битовый флаг */
/1.1/     <1> /* номер */ <0> /* битовый флаг */ <1> /* номер */ <1> /* битовый флаг */

то это условие выполнено не будет, так как первые компоненты номеров узлов равны, а дальше в первом значении идет единица, а во втором ноль (флаг перехода на новый уровень). Получается, что второе значение меньше первого, а это неправильно. Что бы решить эту проблему значения всех не последних в своем уровне компонентов номеров узлов кодируются на единицу больше. То есть наши значения будут закодированы следующим образом:

/1/        <1> /* номер */ <1> /* битовый флаг */
/1.1/     <2> /* номер */ <0> /* битовый флаг */ <1> /* номер */ <1> /* битовый флаг */

Итак, давайте собирать все вместе. Попробуем закодировать какое-нибудь значение, а затем сравним наш результат с тем, что вернет SQL сервер. Пусть это будет значение /5.11/3/

1. Выписываем составные части битовой последовательности

<6> /* номер 5 + 1 */ <0> /* битовый флаг */
<11> /* номер */ <1> /* битовый флаг */
<3> /* номер */ <1> /* битовый флаг */

2. Кодируем отдельные компоненты

6 /* диапазон 4-7 */ -> 100 /* код диапазона*/ 10 /* значение 6 — 4 = 2 */
11 /* диапазон 8-15 */ -> 101 /* код диапазона */ 011  /* значение 11 — 8 = 3 */
3 /* диапазон 0-3 */ -> 01 /* код диапазона */ 11 /* значение 3 — 0 = 3 */

3. Итого получаем:

100 10 0
101 011 1
01 11 1

или

1001 0010 1011 1011 1100 0000

92 BB C0

4. Сравниваем с тем, что вернет SQL сервер:

SELECT Convert(HierarchyId, ‘/5.11/3/’)

Результат:

ЧТД

(с) Ян Либерман

Социальные закладки: