Добавил пользователь Владимир З.
Обновлено: 19.09.2024

Использование HierarchyID в SQL Server на простых примерах

Вы еще используете родительско-дочерний подход или хотели бы попробовать что-то новое типа hierarchyID? Да, это относительно новое, поскольку hierarchyID появился в SQL Server 2008. Конечно, новизна, сама по себе, не является аргументом. Однако заметьте, что Microsoft добавил эту функциональность для лучшего представления многоуровневых отношений один-ко-многим.

Вам может быть интересно, чем это отличается от обычных отношений родитель/ребенок, и какие преимущества дает использование hierarchyID. Если вы никогда не рассматривали этот вопрос, результат может оказаться для вас неожиданным.

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

Но прежде чем мы углубимся в особенности использования hierarchyID, давайте проясним его смысл и область применения.

Что такое HierarchyID?

HierarchyID - это встроенный тип данных в SQL Server, предназначенный для представления деревьев, которые являются наиболее распространенным типом иерархических данных. Каждый элемент дерева называется узлом. В табличном формате это строка со столбцом типа данных hierarchyID.

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

Если выполнить запрос к таблице со столбцом hierarchyID, вы увидите шестнадцатеричные числа. Это одно из визуальных представлений узла. Другим представлением является строка:

'/' - указывает на корневой узел;
‘/1/’, ‘/2/’, ‘/3/’ or ‘/n/’ - представляет потомков - прямые потомки от 1 до n;
‘/1/1/’ or ‘/1/2/’ - это потомки потомков или "внуки". Строка типа '/1/2/' означает, что первый потомок от корня имеет двух детей, которые, в свою очередь, являются двумя внуками корня.

Вот пример того, как это выглядит:

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

Методы HierarchyID

Одним из имеющихся методов является IsDescendantOf. Он возвращает 1, если текущий узел является потомком значения hierarchyID.

Вы можете написать подобный код с использованием этого метода:

Другими методами, используемыми с hierarchyID являются:

• GetRoot - статический метод, который возвращает корень дерева.
  
• GetDescendant - возвращает дочерний узел родителя.
  
• GetAncestor - возвращает hierarchyID, представляющий n-го предка заданного узла.
  
• GetLevel - возвращает целое число, представляющее глубину узла.
  
• ToString - возвращает строку с логическим представлением узла. ToString вызывается неявно, когда имеет место преобразование из hierarchyID в строковый тип.
  
• GetReparentedValue - перемещает узел от старого родителя к новому.
  
• Parse - действует противоположно ToString. Он преобразует строковое представление значения hierarchyID к шестнадцатеричному.
  

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

Чтобы гарантировать максимально быстрое выполнение запросов к таблицам, использующим hierarchyID, вам потребуется проиндексировать столбец. Имеется две стратегии индексирования:

DEPTH-FIRST (сначала в глубину)

В индексе depth-first строки поддерева находятся рядом друг с другом. Это подходит таким запросам, как поиск отделов, их подразделений и сотрудников. Другой пример - управляющий и его подчиненные, которые сохраняются рядом.

В таблице вы можете реализовать индекс depth-first путем создания кластеризованного индекса на узлах. Теперь мы выполняем один из наших примеров именно так.

Рис.2. Стратегия индексирования в глубину. На схеме организации выделено поддерево Chief Engineer и результирующий набор. Список отсортирован для каждого поддерева.

BREADTH-FIRST (сначала в ширину)

В индексе breadth-first строки одного уровня находятся рядом. Это подходит запросам типа найти всех сотрудников, непосредственно подчиняющиеся руководителю. Если большинство запросов подобно этому, создайте кластеризованный индекс на основе (1) уровня и (2) узла.

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

Нужен ли вам индекс depth-first, breadth-first или же оба, зависит от конкретных требований. Требуется найти баланс между важностью типа запросов и операторов DML, которые вы адресуете к таблице.

Ограничения HierarchyID

• SQL Server не может угадать родителя ребенка. Вы должны определить дерево в таблице.
  
• Если вы не используете ограничение уникальности, генерируемое значение hierarchyID может оказаться неуникальным. Решение этой проблемы лежит на разработчике.
  
• Связь родительского и дочернего узлов не поддерживается по аналогии с ограничением внешнего ключа. Следовательно, перед удалением узла, нужно выполнить запрос на наличие существующих потомков.
  

Визуализация иерархий

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

Что касается меня, то с трудом.

Поэтому мы будем использовать Power BI и Hierarchy Chart от Akvelon, наряду с нашими таблицами базы данных. Они помогут отобразить иерархию в организационной структуре. Я надеюсь, что это упростит работу.

Теперь перейдем к работе.

Использование HierarchyID

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

В этой статье мы используем часть структуры организации и цепочку командования на круизном лайнере. Структура была адаптирована из следующей организационной схемы. Посмотрите на рисунок 4 ниже:

Рис.4: Структура организации типичного круизного лайнера, представленная с помощью Power BI, Hierarchy Chart от Akvelon и SQL Server. Имена вымышлены и не имеют отношения к конкретным людям и судам.

• Vessels - таблица для списка круизных судов.
  
• Ranks - таблица званий экипажа. Тут устанавливается иерархия с помощью hierarchyID.
  
• Crew - списочный состав экипажа каждого судна и их звания.
  

Вставка данных в таблицы с HierarchyID

Первая задача в использовании hierarchyID - это добавление записей в таблицу со столбцом hierarchyID. Это можно сделать двумя способами.

Использование строк

Наиболее быстро вставить данные с hierarchyID можно с использованием строк. Чтобы увидеть это в действии, давайте добавим несколько записей в таблицу Ranks.

Этот код добавляет 20 записей в таблицу Ranks.

Как видно, структура дерева определяется в операторе INSERT. Это довольно легко, когда мы используем строки. Кроме того, SQL Server преобразует их в соответствующие шестнадцатеричные значения.

Использование Max(), GetAncestor() и GetDescendant()

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

Чтобы это сделать, получим последний узел, используемый родителем или предком. Мы выполним это при помощи функций Max() и GetAncestor(). Вот как это выглядит:

• Сначала нам нужна переменная для последнего узла и непосредственный начальник.
  
• Последний узел вы можем запросить с помощью MAX(RankNode) для указанного родителя или непосредственного начальника. В нашем случае это Assistant F&B Manager с значением узла 0x7AD6.
  
• Затем, чтобы гарантировать отсутствие появления дубликата потомка, воспользуется @ImmediateSuperior.GetDescendant(@MaxNode, NULL). Значение в @MaxNode - последний потомок. Если это не NULL, GetDescendant() возвращает следующее возможное значение узла.
  
• Наконец, GetLevel() возвращает уровень вновь созданного узла.
  

Получение данных

После добавления записей в вашу таблицу, самое время запросить их. Для это есть 2 способа.

Запрос для прямых потомков

• Значение узла управляющего или родителя
  
• Уровень сотрудника этого управляющего
  

Результат выполнения запроса показан на рисунке 5:

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

Запрос для поддеревьев

Иногда также требуется получить список потомков и потомков потомков до самого нижнего уровня. Чтобы сделать это, нам необходимо иметь hierarchyID родителя.

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

Рис.6: Директор отеля и все подчиненные до последнего уровня

Перемещение узлов с HierarchyID

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

Потенциальная проблема

• Во-первых, перемещение узла связано с вводом/выводом. Насколько часто вы перемещаете узлы может стать решающим фактором, если вы используете hierarchyID или обычную схему родитель/потомок.
  
• Во-вторых, перемещение узла в схеме родитель/потомок приводит к обновлению одной строки. В то же время, когда вы перемещаете узел с hierarchyID, обновление затрагивает одну или более строк. Число задействованных строк зависит от глубины уровня иерархии. Это может вызвать серьезные проблемы с производительностью.
  

Решение

Давайте рассмотрим используемую здесь схему.

• Члены команды перемещаются более часто, чем их должность на судне. Эта схема уменьшит перемещение узлов в иерархии. Как следствие, это минимизирует описанную выше проблему.
  
• Определение более одной иерархии в таблице Crew усложняет дело, т.к. два судна должны иметь двух капитанов. В результате имеем два корневых узла.
  
• Если вам потребуется вывести все должности с указанием соответствующего члена команды, вы можете использовать LEFT JOIN. Если на борту нет никого в этой должности, будет получена пустая ячейка для этой позиции.
  

Рис.7: Три желтых узла размещены неправильно в иерархии - Cruise Staff, Head Waiter и Waiter.

Перемещение узла, не имеющего потомков

• Определить hierarchyID дочернего узла, который требуется переместить.
  
• Определить hierarchyID старого родителя.
  
• Определить hierarchyID нового родителя.
  
• Использовать UPDATE совместно с GetReparentedValue() для физического перемещения узла.
  

Как только узел обновился, для узла будет использоваться новое шестнадцатеричное значение. После обновления моего подключения Power BI к SQL Server схема иерархии изменится следующим образом:

Рис.8: Узел Cruise Staff исправлен и перемещен к надлежащему родителю.

На рисунке 8 Cruise Staff больше не подчиняется Cruise Director - подчитение перешло к Assistant Cruise Director. Сравните с рисунком 7 выше.

Теперь давайте перейдем к следующей стадии и переместим Head Waiter к Assistant F&B Manager.

Перемещение узла с потомком

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

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

В этом примере мы должны получить такую проблему: Asst. F&B Manager имеет дочерний узел Bartender.

В этом примере итерация начинается с необходимости передать узел дочернему элементу на последнем уровне.

После выполнения кода таблица Ranks обновится. И опять, если вы хотите увидеть изменения, обновите отчет в Power BI. Вы увидите следующие изменения:

Рис.9: Все дочерние узлы Asst. F&B Manager исправлены

Преимущества использования HierarchyID по сравнению с моделью родитель/ребенок

Чтобы убедить кого-нибудь что-нибудь использовать, нужно осознавать выгоды.

Поэтому в этой части мы сравним операторы, использующие те же самые таблицы, приведенные в начале. Один будет использовать hierarchyID, а другой - подход родитель/ребенок. Результирующие наборы будут одинаковы для обоих подходов. Мы ожидаем такие, как на рисунке 6.

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

Упрощение кода

Посмотрите код ниже:

Этот образец требует только значения hierarchyID. Вы можете при желании изменить значение, не меняя запрос.

Теперь сравните оператор для модели родитель/ребенок, дающий тот же самый результат:

Что вы думаете? Пример почти тот же за исключением одного момента.

Предложение WHERE во втором запросе не получится гибко адаптировать, если потребуется другое поддерево.

Сделайте второй запрос достаточно общим, и размер вашего кода увеличится.

Более быстрое выполнение

Согласно Microsoft, "запросы поддеревьев существенно быстрей с использованием hierarchyID" по сравнению со схемой родитель/потомок. Давайте это проверим.

Мы используем те же самые запросы. Одной из значимых метрик производительности является число логических чтений, которую можно получить с помощью установки SET STATISTICS IO. Она скажет, сколько 8Кб страниц потребуется прочитать SQL Server, чтобы получить нужный нам результат. Чем выше значение, тем к большему числу страниц SQL Server должен получить доступ и прочитать, и тем медленнее выполняется запрос. Выполните SET STATISTICS IO ON, а затем повторно запустите два вышеприведенных запроса. Запрос с меньшим числом логических чтений победит.

Рис.10: Запрос, использующий hierarchyID выполняется лучше с меньшим числом логических чтений

Анализ

• Таблица Vessel самая заметная из трех таблиц. Использование hierarchyID требует только 2*8Кб=16Кб, которые SQL Server должен прочитать из кэша (памяти). Между тем, использование схемы родитель/потомок требует чтения 26*8Кб=208Кб - существенно выше, чем при использовании hierarchyID.
  
• Таблица Ranks, которая включает определение иерархий, требует 92*8Кб=736Кб. С другой стороны, использование схемы родитель/потомок требует 132*8Кб=1056Кб.
  
• Таблица Crew требует 2*8Кб=16Кб для обоих подходов.
  

• Добавить подходящие индексы
  
• Реструктурировать запрос
  
• обновить статистику
  

Но зачем обращаться к логическим чтениям, а не к затраченному времени?

Проверка затраченного времени (elapsed time) для обоих запросов с помощью SET STATISTICS TIME ON обнаруживает незначительное расхождение в миллисекундах для нашего небольшого набора данных. Кроме того, ваш сервер разработки может иметь отличную аппаратную конфигурацию, настройки SQL Server и рабочую нагрузку. Затраченное время менее миллисекунды может ввести вас в заблуждение относительно того, быстро выполняется ваш запрос или нет.

Пошли дальше

SET STATISTICS IO ON не открывает вам вещи, которые происходят "под капотом". В этом параграфе мы выясним, почему SQL Server приходит к этим числам, изучая план выполнения.

Давайте начнем с плана выполнения первого запроса.

Рис.11: План выполнения первого запроса с hierarchyID

Теперь посмотрите план выполнения второго запроса.

Рис.12: План выполнения второго запроса, использующего модель родитель/ребенок

Сравнивая рисунки 11 и 12, мы видим, что SQL Server требуются дополнительные усилия для получения результата, если вы используете подход родитель/ребенок. За это усложнение отвечает предложение WHERE.

Однако виной всему может быть и структура таблицы. Мы использовали одну и ту же таблицу для обоих подходов: таблица Ranks. Итак, я попытался продублировать таблицу Ranks, но использовать разные кластеризованные индексы, соответствующие каждой процедуре.

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

Иерархические структуры данных в реляционных БД

Примеры, приводимые далее, были созданы и протестированы с помощью Interbase 6.

Иерархии данных

Чтобы обсудить проблему хранения иерархии в реляционной БД, мы вначале рассмотрим вопрос о том, какие же иерархии данных могут встретиться на практике. В реальной жизни иерархии имеют, как правило, некоторые ограничения. Учитывая эти ограничения, можно построить более эффективные процедуры обработки иерархических данных.

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

Рассмотрим некоторые варианты представления иерархических структур в реляционных БД.

Возможные варианты структур БД для хранения иерархий

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

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

Сложность вычисления уровня вложенности произвольного элемента.

Сложность получения всех (в том числе и не прямых) потомков данного узла.

Дальнейшее рассмотрение мы будем вести на примере построения иерархической структуры – тематического каталога библиотеки. Данный каталог применяется для классификации, сортировки и поиска книг по их содержанию. Будем считать, что каждый элемент каталога описывается собственным неуникальным символьным именем. Для обеспечения уникальности записей для каждого элемента каталога необходимо ввести первичный ключ. Для поддержки иерархичности данных введем дополнительное поле-ссылку на предка данного элемента иерархии. Ниже приведено описание полученной структуры на языке SQL:

Данная структура является минимально необходимой и достаточной для организации и хранения иерархии. Назовем ее структурой со ссылкой на предка . В данной структуре присутствует как минимум один недостаток – отсутствие контроля правильности ссылки на родителя. Какие же значения поля PARENT_ID являются правильными? Ответ очевиден – весь диапазон значений первичного ключа (поля ID) + одно значение, используемое для обозначения отсутствия родительского элемента. Данное значение необходимо для ввода и хранения корневых элементов иерархии. Чаще всего в качестве значения, обозначающего отсутствие родителя, используется NULL, хотя нет никаких физических ограничений для использования других значений. Так, например, если вы уверены, что значения первичного ключа будут больше 0, в качестве признака корневого элемента можно использовать значение (–1) или другие отрицательные значения в поле PARENT_ID. Я не буду оригинален и в качестве значения PARENT_ID для корневых элементов использую NULL. Тогда для контроля правильности PARENT_ID можно использовать следующее ограничение:

Вернемся к отмеченным выше недостаткам данной структуры (сложность формирования полного пути и вычисления уровня элемента). Эти недостатки вытекают из того простого факта, что в данной структуре информация о полном пути и уровне нигде не хранится. Решить проблему быстрого получения уровня вложенности можно введением в структуру таблицы дополнительного поля Level. Описание таблицы тогда будет выглядеть так:

Структура для хранения иерархии с неограниченным числом уровней вложенности и потомков готова.

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

• Ссылка на предка
• Информация о первом элементе уровня иерархии
• Информация о втором элементе уровня иерархии
• …
• Информация о n-ном элементе уровня иерархии, где n – количество максимальное количество потомков

Ссылка на предка содержит в себе ссылку на запись, хранящую информацию о предыдущем уровне иерархии и смещение (номер столбца) с описанием родителя.

В нашем примере мы ограничим количество предков числом 5, тогда SQL-описание таблицы будет выглядеть следующим образом:

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

Одним из вариантов хранения таких иерархий является поуровневое хранение в различных таблицах. Например, таблица CATALOG_LEVEL_1 хранит все элементы первого уровня вложенности, таблица CATALOG_LEVEL_2 – второго, и т.д. Ниже приведено описание такой структуры для случая трехуровневой иерархии.

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

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

Первый тип приведен ниже:

Весь фокус в принципе формирования первичного ключа ID. Позиция последнего ненулевого десятичного разряда ключа – это уровень элемента, а цифра в этой позиции – номер элемента на данном уровне. Например, первый элемент первого уровня будет иметь второй – 00002. На втором уровне третий элемент, имеющий предком первый элемент первого уровня, будет иметь и т.д. Данная структура хороша при равномерном распределении элементов по уровням. Ее мы назовем структурой с поразрядным ключом . В зависимости от того, справа или слева находится разряд, кодирующий первый уровень, можно выделить структуру с поразрядным правым ключом и структуру с поразрядным левым ключом . В нашем случае я описал правый ключ. Если же максимальное число элементов конечно, но различно для различных ветвей дерева, и хотя бы приблизительно может быть оценено для каждой ветви, можно воспользоваться следующей структурой:

Данная структура является модификацией структуры для хранения иерархии с неограниченным уровнем вложенности и количеством потомков. В структуру добавлены поля LOW и HIGH для хранения начала и конца диапазона первичных ключей всех потомков данного элемента. Такая иерархия может быть представлена набором отрезков (см. рисунок). Это позволяет быстро и легко выбрать всех потомков данного элемента. Данную структуру назовем структурой с хранением границ ветви .

Итак, мы рассмотрели несколько различных типов структур для хранения иерархий. Далее мы рассмотрим решение задач, связанных с использованием этих структур:

• получения потомков элемента;
• получения уровня вложенности элемента;
• получения полного пути от элемента до корня иерархии;
• операции вставки, удаления, перемещения элемента и его потомков для вышеперечисленных структур.

Получение непосредственных потомков

Получение потомков элемента является основной задачей при построении и отображении дерева. Далее мы рассмотрим получение потомков для:

структур со ссылкой на предка

К этому виду структур относится и модификация с поддержкой информации об уровне элемента, а также структура с хранением границ ветви. Очевидно, что в такой структуре потомками элемента будут все элементы, ссылающиеся на данный (PARENT_ID потомков равен ID родителя). Запрос на выборку потомков (имена таблицы и полей взяты из приведенных выше описаний) выглядит так:

структур с потабличным хранением уровней

В данной структуре для определения потомков необходимо знать уровень вложенности предка. Зная уровень вложенности, можно определить имя таблицы, в которой хранится информация о потомках. Запрос на выборку потомков:

Например, для определения потомков узла второго уровня с и PARENT_ID = 5 запрос будет:

структур с поразрядным ключом

При структуре с поразрядным правым ключом непосредственные потомки имеют первичные ключи c ненулевым следующим разрядом и таким же, как первичный ключ предка числом в младших разрядах. В ранее рассмотренном нами случае потомки первого корневого элемента (ID = 1) будут иметь ID 11,21,31,41, …91. Запрос на выборку:

SELECT “ID” FROM “CATALOG4” WHERE “ID” IN (11,21,31,41,51,61,71,81,91)

Структура с левым ключом для первого корневого элемента (ID = 10000) потомки 11000, 12000,13000…19000.

Получение всех потомков

Довольно часто возникает задача получения всех, в том числе и не прямых потомков данного элемента. Рассмотрим решение этой задачи для приведенных структур.

структура со ссылкой на предка и ее модификация с поддержкой информации об уровне элемента

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

структура с потабличным хранением уровней

Потомки данного элемента содержатся в “нижележащих” таблицах и имеют как часть составной ссылки на предка в одном из полей значение ID предка. Общий список потомков можно получить объединением (UNION) запросов.

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

структура с поразрядным ключом

В данной структуре содержится информация о полном пути к элементу. Это облегчает выборку всех потомков.

Левый ключ

Для первого корневого элемента диапазон ID потомков будет 10001… 19999, для второго 20001…29999 и т.д.

Правый ключ

Ну, здесь тоже все просто. Первый элемент иерархии на втором уровне его первый предок 11 и т.д. Таким образом, потомки будут иметь в конце ID цифры, совпадающие с ID предка.

структура с хранением границ ветви

Элементы структуры LOW и HIGH хранят границы диапазона первичных ключей всех потомков.

Получения уровня вложенности элемента

Часто уровень вложенности элемента иерархии привязан к какому-либо классификационному признаку предметной области. Отсюда возникает задача определения уровня вложенности произвольного элемента.

структура со ссылкой на предка, структура с хранением границ ветви

Построение полного пути к корню дерева и определение числа предков. Довольно неудобно, но другого способа нет.

структура со ссылкой на предка и хранением уровня вложенности

Недаром мы ввели поле для хранения уровня вложенности. Оно-то и содержит нужную нам информацию.

структура с потабличным хранением уровней

Уровень вложенности определяется таблицей, в которой хранится запись об элементе.

структура с поразрядным ключом

Уровень вложенности определяется положением последнего ненулевого разряда в ключе.

Получения полного пути от элемента до корня иерархии

структура со ссылкой на предка и ее модификация с поддержкой информации об уровне элемента, структура с хранением границ ветви

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

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

Полный путь содержится в первичном ключе элемента.

Операции вставки, удаления, перемещения элемента и его потомков

структура со ссылкой на предка

Добавление нового элемента:

Удаление элемента: Кроме непосредственно самого элемента необходимо удалить и его потомков. Проблема решается введением триггера:

Перемещение элемента: надо просто поменять ссылку на родителя.

структура со ссылкой на предка и поддержкой уровней

Можно использовать запросы, аналогичные случаю с базовой структурой. Для проверки корректности поля Level можно ввести дополнительные триггеры:

структура с потабличным хранением уровней

Запросы на вставку и перемещения тривиальны, и потому не приводятся. При удалении элемента можно ввести дополнительный триггер для удаления потомков, аналогично триггеру для структуры со ссылкой на предка.

структура с хранением границ ветви

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

На этом теорию заканчивается и начинается практика. Предположим нужно сделать каталог ресурсов с категориями неограниченой вложенности. При этом перед программистом возникает несколько микро-задач:

* Нужно сделать вывод дерева категорий
* Нужно получить список ВСЕХ подкатегорий для указанной категории
* Нужно получить список подкатегорий, уровень вложенности которых на единицу больше уровня вложенности указанной категории
* Нужно получить список всех родительских категорий для указанной категории (для посторения пути к текущей категории)

Замечу, что класс CDBTree еще хранит в таблице уровень вложенности для данного узла. Это факт облегчит нам решение задачи номер 3 Для начала создайте таблицу:

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

Данный пример просто заполняет таблицу (просто чтобы следующие примеры потестить на ней).
Думаю код здесь ясен. Наверное стоит лишь объяснить строку:

Данная строка вставляет корневой узел в таблицу. Корневой узел должен быть один. Также следует заметить, что этот метод очищает таблицу, перед вставкой, так что будьте осторожны.
Теперь давайте выведем дерево. Для этого достаточно просто вывести все элементы, отсортировав их по cleft:

В данном случае для расчета величины отступа используется значение clevel. Теперь посмотрим, как получить все подкатегории. Это можно сделать либо с помощью метода enumChildrenAll($cid); либо написав правильный SQL-запрос. Предположим есть категория параметры которой $cleft, $cright и $clevel. Тогда запрос, получающий все дочерние узлы, выглядит так:

Выполнив этот запрос, вы получите все подкатегории для указанной категории Метод enumChildrenAll($cid); также возвращает подкатегории, но он возвращает только их идентификаторы, и нет встроенных методов для того чтобы он возвращал дополнительные поля (конечно же вы можете внести изменения в класс).

Для получения списка подкатегорий, уровень вложенности которых на единицу больше уровня вложенности указанной категории происходит.

И последнее — определение родительских категорий.
Запрос должен выглядеть так:

В классе CDBTree для этого есть метод enumPath($cid).
Теперь об рекомендациях автора класса:

Также добавлю, что автор класса рекомендует использовать его (класс) только для добавления/удаления узлов в дерево, а для получения узлов писать SELECT-запросы самому.

Описание методов класса CDBTree

CDBTree(&$DB, $tableName, $itemId, $fieldNames=array())
конструктор
Параметры:

* &$DB — ссылка на объект класса CDatabase (этот класс лежит в архиве с dbtree.php);
* $tableName — имя таблицы, в которой лежит "дерево";
* $itemID — имя первичного ключа таблицы в которой лежит "дерево";
* $fieldNames — массив с именами полей таблицы

function getElementInfo($ID)
Возвращает массив с информацией о об элементе с указанным $ID (параметры left, right, level).
function clear($data=array())
данная функция очищает таблицу и вставляет в нее корневой узел дерева.
В массиве $data должна быть информация в виде array("db_field"=>"value", …)
Поля left, right и level будут вставлены автоматически.
function update($ID, $data)
этот метод используется для изменения информации об указанном элементе. Параметры:

* $ID — идентификатор узла
* $data — массив с обновленными данными. (параметры left, right и level вставлять не нужно)

function insert($ID, $data)
Метод для вставки узла в дерево. Параметры:

* $ID — идентификатор родительского узла
* $data — массив с обновленными данными. (параметры left, right и level вставлять не нужно)

function delete($ID)
Удаляет указанный узел не удаляя его "потомков";
function deleteAll($ID)
Удаляет указанный узел вместе с его "потомков";
function enumChildrenAll($ID)
Определяет всех "потомков" для указанного узла
function enumChildren($ID, $start_level=1, $end_level=1)
Определяет потомков для указанного узла

* $start_level — начальный уровень вложенности узла с которого нужно искать "потомков";
* $end_level — конечный уровень вложенности узла до которого нужно искать "потомков";
Если $end_level не указан, (равен 0) то ищутся все узлы "глубже" $start_level

function enumPath($ID, $showRoot=false)
Определяет всех родителей для указанного узла.

* $showRoot — true, если нужно выводить корневой элемент.

Последние три описанные функции формируют SQL-запрос таким образом, что выводятся только идентификаторы узла.

Остальные методы мне использовать не приходилось. Поэтому описывать их не буду. В последней версии класса появился метод MoveAll для перемещения узлов в дереве, но пока он работает с багами.

Список смежности
Это интуитивно понятный способ организации дерева: замыкаем связь таблицы на саму себя (рефлексивная связь), рис. 1.

WITH Поддерево ([Код территории], [Код вышестоящей территории], Наименование, Уровень) AS
(
SELECT [Код территории], [Код вышестоящей территории], Наименование, 1
FROM Территории
WHERE [Код вышестоящей территории] = 40288000 — корень поддерева или IS NULL для корня целого дерева
UNION ALL
SELECT Территории.[Код территории], Территории.[Код вышестоящей территории], Территории.Наименование, Уровень + 1
FROM Территории
INNER JOIN Поддерево ON Территории.[Код вышестоящей территории] = Поддерево.[Код территории]
WHERE Территории.[Код вышестоящей территории] IS NOT NULL
)
SELECT [Код территории], [Код вышестоящей территории], Наименование, Уровень
FROM Поддерево

Выборка всех предков (путь к узлу от корня):

WITH Поддерево ([Код территории], [Код вышестоящей территории], Наименование, Уровень) AS
(
SELECT [Код территории], [Код вышестоящей территории], Наименование, 1
FROM Территории
WHERE [Код территории] = 40288000 — узел
UNION ALL
SELECT Территории.[Код территории], Территории.[Код вышестоящей территории], Территории.Наименование, Уровень + 1
FROM Территории
INNER JOIN Поддерево ON Территории.[Код территории] = Поддерево.[Код вышестоящей территории]
)
SELECT [Код территории], [Код вышестоящей территории], Наименование, (SELECT MAX(Уровень) FROM Поддерево) — Уровень
FROM Поддерево

WITH Поддерево ([Код территории], [Код вышестоящей территории], Наименование, Уровень) AS
(
SELECT [Код территории], [Код вышестоящей территории], Наименование, 1
FROM Территории
WHERE [Код территории] = 40288000 — узел, проверяемый на вхождение
UNION ALL
SELECT Территории.[Код территории], Территории.[Код вышестоящей территории], Территории.Наименование, Уровень + 1
FROM Территории
INNER JOIN Поддерево ON Территории.[Код территории] = Поддерево.[Код вышестоящей территории]
)
SELECT result =
CASE
WHEN EXISTS(
SELECT 1 FROM Поддерево
WHERE [Код территории] = 40260000 /* корень поддерева */)
THEN ‘Узел входит в поддерево’
ELSE ‘Узел НЕ входит в поддерево’
END

В реляционном же виде схема представлена на рис. 3.

Но за излишества надо платить. Целостность данных будет поддерживаться триггерами, которые перезаписывают список и уровни предков данного узла при его изменении. Для операции удаления достаточно декларативной ссылочной целостности (каскадное удаление), если ваша СУБД его поддерживает.
Если за образец принять список смежности, который не содержит никакой избыточности, то для метода подмножеств на каждый уровень потребуется столько дополнительных записей в таблице подмножеств, сколько элементов находится на данном уровне дерева, умноженном на номер уровня (вершину считаем первым уровнем). Количество записей растет в арифметической прогрессии.
Однако стоит взглянуть на примеры все тех же типовых запросов, как становятся очевидными преимущества, полученные от избыточности хранения: запросы стали короткими и быстрыми.
Выборка поддерева по заданному узлу:
SELECT [Код подмножества], Уровень
FROM Подмножества
WHERE [Код множества] = 123 — корень поддерева
ORDER BY Уровень
Выборка всех предков (путь к узлу от корня):
SELECT [Код множества], Уровень
FROM Подмножества
WHERE [Код подмножества] = 345 — узел
ORDER BY Уровень

Проверка вхождения узла в поддерево:

SELECT result =
CASE
WHEN EXISTS(
SELECT 1 FROM Подмножества
WHERE [Код подмножества] = 345 /* узел */
AND [Код множества] = 211 /* корень поддерева */)
THEN ‘Узел входит в поддерево’
ELSE ‘Узел НЕ входит в поддерево’
END

Маршрут обхода
Как известно из уже упомянутой теории графов, для обхода дерева существует три способа: можно проходить узлы в префиксном, инфиксном или суффиксном порядке. Префиксный порядок обхода дерева рекурсивно определяется так: сначала корень дерева, потом узлы левого поддерева в префиксном порядке, наконец, узлы правого поддерева в префиксном порядке. Сложно? Взгляните на рис. 4, и все станет предельно ясно.

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

SELECT *
FROM [Территории 4]
WHERE Путь LIKE ‘1.2%’ — корень поддерева
ORDER BY Путь

Выборка всех предков:

SELECT *
FROM [Территории 4]
WHERE ‘1.2.1’ /* узел */ LIKE Путь + ‘%’
ORDER BY Путь

SELECT T1.*
FROM [Территории 4] T1, [Территории 4] T2
WHERE T2.Путь LIKE T1.Путь + ‘%’
AND T2.Наименование like ‘МО Рыбацкое’

Проверка вхождения узла в поддерево:

SELECT result =
CASE
WHEN EXISTS(
SELECT 1 FROM [Территории 4] as T1, [Территории 4] as T2
WHERE T1.Наименование = ‘МО Рыбацкое’ /* узел */
AND T2.Наименование = ‘Невский район’ /* корень поддерева */
AND T1.Путь LIKE T2.Путь + ‘%’)
THEN ‘Узел входит в поддерево’
ELSE ‘Узел НЕ входит в поддерево’
END

Оптимизация
Зная заранее максимальное количество уровней и максимальное число прямых потомков, можно обойтись без разделителей, используя числовые коды с фиксированной разбивкой на группы разрядов. Пустые лидирующие разряды заполняются нулями.
Подобная система используется во многих межсистемных классификаторах, например относящихся к государственному стандарту ОКАТО (Общероссийский классификатор объектов административно-территориального деления) или NAICS (North American Industry Classification System — Североамериканская система классификации отраслей экономики).

Читайте также:

  
• Как собрать дерево глицинию из бисера
  
• Лица совершившие незаконную порубку или повреждение деревьев в населенных пунктах несут
  
• Воздействие дерева на организм человека
  
• Где лучше держать денежное дерево
  
• Зачем автор приводит описание сосны и ели сросшихся корнями