Історія ORDPATH в SQL сервері
Тип даних HierarchyId
Формування ієрархії (привласнення кодів новим вузлів)
Сортування HierarchyId значень
Типові запити до ієрархічним даними
Історія ORDPATH в SQL сервері
- Ієрархія зберігається і зчитується цілком.
- Додатком потрібні ці дані саме в XML-форматі.
- Пошуки за даними XML документа виконуються рідко і не критичні за часом.
Для того щоб не виконувати парсинг XML-документа кожен раз, коли потрібно в ньому щось знайти, призначений первинний XML-індекс. При створенні такого індексу XML-документ зберігається в базі даних в зручному реляционном вигляді, що потім дозволяє набагато ефективніше виконувати пошук по ньому. Щоб уявити ієрархію елементів, в цьому індексі використовується ORDPATH-схема (ORDPATH - hierarchical labeling scheme). Такий підхід виявився в даному випадку більш ефективний, ніж традиційний "Parent / Child".
Тип даних HierarchyId
Представлена вище форма запису HierarchyId значень є логічною. Так HierarchyId значення перетворюються в символьні типи і назад. У бінарному вигляді значення типу HierarchyId зберігаються дуже компактно.
Що ж такого чудового в цій схемі присвоєння кодів вузлів (ORDPATH-схемі)?
- Використовуючи цю схему завжди можна додати новий вузол в будь-яке місце ієрархії, не змінюючи існуючі вузли.
- Інформацію про всі батьківських вузлах (від безпосереднього батька до кореневого вузла) присутній в коді вузла.
- Легко ідентифікувати всі дочірні вузли (не тільки безпосередніх нащадків).
- Схема зберігає інформацію не тільки про зв'язок батько / нащадок, але і про порядок проходження вузлів (вузол / 1/1 / йде раніше вузла / 1/2 /).
- Сортування по стовпцю HierarchyId вибудовує вузли ієрархії (рядки таблиці) в "правильному" порядку.
Формування ієрархії (привласнення кодів новим вузлів)
Перш ніж розбиратися з тим, як формуються нові коди вузлів при додаванні їх в ієрархію, давайте створимо тестову табличку, яка буде зберігати нашу ієрархію:
Нагадаю, що в логічній (текстової) формі HierarchyId-значення є список номерів всіх вузлів по шляху від кореня ієрархії до деякого заданого вузла, розділених символом «/». Кожен номер вузла складається з одного або декількох компонентів (чисел), розділених символом «.» (Крапка). Приклад коректних HierarchyId-значень:
Фізична кодування HierarchyId значень, очевидно, повинна відповідати таким вимогам:
- Повинна бути якомога більш компактною.
- Повинна забезпечувати "правильний" порядок сортування HierarchyId значень (тобто, наприклад, значення /0.1/0.2/ має бути більше, ніж значення /0.1/0/).
Тобто, наприклад, значення /7/4.5/ кодується згідно з цією схемою так:
Кожен компонент номера вузла складається з двох частин - коду діапазону і власне значення. У таблиці 1 представлені всі використовувані SQL-сервером діапазони. Наприклад, якщо потрібно закодувати значення 11, то, згідно з таблицею, буде використаний діапазон 8-15 і, відповідно, двійкове подання цього компонента буде одно:
101 / * код діапазону 8-15 * /
011 / * значення, перелічене на початок діапазону (11 - 8 = 3) * /
Очевидно, що бітові послідовності, що кодують HierarchyId-значення, має змінну довжину. Причому їх довжина зовсім не обов'язково буде кратна восьми бітам (кордонів байт). Так як же визначити довжину HierarchyId-значення? Бітовий прапор переходу на новий рівень в останньому компоненті останнього номера вузла завжди дорівнює одиниці. Далі бітова послідовність доповнюється нулями до кордону байта. Відповідно, щоб знайти справжню довжину HierarchyId-значення в бітах, потрібно просто знайти перший дорівнює одиниці біт праворуч в останньому байті - це і є кінець послідовності.
Давайте згадаємо про вимогу «правильної» сортування HierarchyId значень. Згідно цій вимозі, наприклад, значення / 1 / повинно бути менше значення /1.1/. Але якщо закодувати ці значення так:
то ця умова виконана не буде, так як перші компоненти номерів вузлів рівні, а далі в першому значенні йде одиниця, а в другому - нуль (прапор переходу на новий рівень). Виходить, що друге значення менше першого, а це неправильно. Щоб вирішити цю проблему значення всіх не останніх в своєму рівні компонентів номерів вузлів мають значення на одиницю більше. Тобто наші значення будуть закодовані наступним чином:
Отже, давайте збирати все воєдино. Спробуємо закодувати якесь значення, а потім порівняємо наш результат з тим, що поверне SQL-сервер. Нехай це буде значення /5.11/3/
- Виписуємо складові частини бітової послідовності: