Ієрархічні довідники з лінійним часом доступу
Гліб Земсков
Вступ
Розробка ієрархічних довідників - достатньо
часто зустрічається завдання в бізнес-додатках. Існує досить багато
алгоритмів зберігання дерева в реляційних СУБД. У даній статті буде розказано
про одну з таких моделей. Її достоїнства - простота реалізації, швидкість
вибірки і додавання нового елемента, а серед недоліків можна виділити
відносну складність вставки і переміщення даних, а також кінцеву глибину
ієрархії. Але ті чи інші недоліки є в будь-якій схемі зберігання
ієрархічних даних в РСУБД.
Наскільки гарний алгоритм
Для ієрархічних довідників ми визначимо кілька
найбільш часто зустрічаються завдань, які зачіпають ієрархію.
отримання всіх нащадків вузла;
отримання безпосередніх нащадків вузла;
додавання нащадка;
видалення вузла з нащадками;
перенесення вузла.
Ієрархія Дьюї (Dewey)
Ієрархічний довідник може бути заснований на
алгоритмі запису, що використовується в системі десяткової класифікації Дьюї (Dewey
Decimal Classification). Нас в даний момент цікавить не сам класифікатор, а
що використовується у ньому принцип. Спробую його описати.
Кожен вузол містить деякий ідентифікатор,
унікальний серед нащадків його батька. Кожен вузол містить шлях від кореневого
елемента до цього. Шлях реалізується за допомогою ідентифікаторів, розділених
символом точки.
Наприклад:
1 Організація «Роги і копита».
1.1 Департамент «Рогу».
1.1.1 Відділ продажу рогів.
1.1.2 Відділ покупки рогів.
1.1.2.1 Група оцінки якості рогів.
1.1.3 Відділ прокату рогів.
1.2. Департамент «Копита»
1.2.1 Відділ покупки копит.
1.2.2 Відділ продажу копит.
Як можна відразу помітити, при роботі з подібним класифікатором
зручно використовувати оператора LIKE. Якщо вказується шлях, в якому початкові
символи не є маскою, база даних може використовувати індекс з операцією
index scan з діапазонним пошуком.
Створимо тестовий приклад.
CREATE TABLE DEPARTMENT
(
ID INT PRIMARY KEY
IDENTITY (1,1),
Path VARCHAR (180) UNIQUE,
Position INT NOT NULL,
NAME VARCHAR (128)
)
GO
INSERT INTO DEPARTMENT (Path, Position, NAME)
VALUES ('1 ', 1,' Організація «Роги і копита »')
INSERT INTO DEPARTMENT (Path, Position, NAME)
VALUES ('1 .1 ', 1,' Департамент «Роги »')
INSERT INTO DEPARTMENT (Path, Position, NAME)
VALUES ('1 .1.1 ', 1,' Відділ продажу рогів ')
INSERT INTO DEPARTMENT (Path, Position, NAME)
VALUES ('1 .1.2 ', 2,' Відділ покупки рогів ')
INSERT INTO DEPARTMENT (Path, Position, NAME)
VALUES ('1 .1.2.1 ', 1,' Група оцінки якості рогів ')
INSERT INTO DEPARTMENT (Path, Position, NAME)
VALUES ('1 .1.3 ', 3,' Відділ прокату рогів ')
INSERT INTO DEPARTMENT (Path, Position, NAME)
VALUES ('1 .2 ', 2,' Департамент «Копита »')
INSERT INTO DEPARTMENT (Path, Position, NAME)
VALUES ('1 .2.1 ', 1,' Відділ покупки копит ')
INSERT INTO DEPARTMENT (Path, Position, NAME)
VALUES ('1 .2.2 ', 2,' Відділ продажу копит ')
GO
Розрахунок довжини поля Path
Перш за все слід уточнити, чому полі Path має
довжину 180. Розрахунок простий. Кількість підлеглих відділів кожного вузла в
довіднику навряд чи може бути більше, ніж тризначна цифра (від 0 до 999
підрозділів). Таке не під силу навіть таким гігантам, як Газпром. Ділимо
кількість зайнятих символів 4 (з огляду на точку) і отримуємо рівень можливих
вкладень - 60. Цифра також позамежна. Можна підійти з іншого боку.
Рівень вкладень навряд чи буде більше 20. Ділимо 180 на 20, і отримуємо 9
символів. 8 символів (враховуючи точку) в десятковій системі - це десять мільйонів
підрозділів. Таким чином, 180 символів в даному випадку достатньо, щоб
описати надмірне число організацій та відділів, але недостатньо, щоб розмір
сильно впливав на продуктивність бази даних. І це при тому, що ми
розраховували найгірші випадки. Насправді, місткість ієрархії
значно більше. Якщо кількість даних більше, то розмір Path можна
збільшити. Але для цього довідника його розміру достатньо. І цього розміру
вистачало для більшості бізнес-додатків, з якими я зустрічався.
Отримання всіх нащадків вузла.
Припустимо, ми збираємося отримати всі підрозділи,
що входять до відділу «Роги і копита».
За допомогою Path батька створюємо простий запит.
SELECT
* FROM DEPARTMENT WHERE Path LIKE '1 .1 .%'
Додавши до умови в операторі LIKE, ми вказали запиту
вибрати всі записи, що мають Path довше, ніж у батьків.
Такий запит також може бути побудований щодо
даних батьківського вузла.
SELECT result .*
FROM DEPARTMENT parent INNER
JOIN DEPARTMENT result
ON (result.Path LIKE
parent.Path +'.%')
WHERE parent.NAME = 'Департамент «Роги»'
Отримання безпосередніх нащадків вузла
Візьмемо попередній запит і додамо негативне
умова для безпосередніх нащадків даного Path.
SELECT * FROM DEPARTMENT
WHERE Path LIKE '1 .1.% 'AND Path NOT LIKE '1 .1 .%.%'
У результаті ми отримаємо всі підлеглі елементи від
вузла "Департамент« Роги »". Можна вибрати відразу декілька рівнів:
SELECT * FROM DEPARTMENT
WHERE Path LIKE '1 .1.% 'AND Path NOT LIKE '1 .1 .%.%.%'
Додавання нащадків.
У даному випадку нам потрібно вставити запис по
певному шляху з унікальним ідентифікатором Position. Створимо підлеглий
елемент вузла із значенням Path 1.1. Унікальність ідентифікатора важлива тільки
для самих нащадків. Тому обчислимо максимальне значення для нащадків даного
батька та додамо до нього одиницю. Якщо на клієнті відомі сусідні елементи,
і можна отримати ідентифікатор Position відразу, то запит не представляє
складності:
INSERT INTO DEPARTMENT (Path, Position, NAME)
VALUES ('1 .1.4 ', 4,' Відділ
прокату копит ')
Якщо Position невідомий, то можна отримати його в
запиті:
INSERT INTO DEPARTMENT (Path, Position, NAME)
SELECT '1 .1 '+'. '+ ISNULL (CAST (MAX (Position) 1 AS VARCHAR), '1'),
ISNULL (MAX (Position) 1, 1),
'Відділ прокату копит'
FROM DEPARTMENT
WHERE Path LIKE '1 .1.% 'AND Path NOT LIKE '1 .1 .%.%'
ПОПЕРЕДЖЕННЯ
У багатокористувацької
середовищі, для деяких баз даних, таких, як MSSQL, подібне додавання
є класичним випадком фантома. Щоб подолати цю проблему,
можна підвищити рівень транзакції до Serializable, використовувати як
поля Position автоінкрементальное полі або просто враховувати, що можна
отримати помилку при вставці однакових значень в унікальний індекс поля
Path.
Видалення вузла з нащадками
Видалення схоже на операцію вибірки за винятком
того, що ми також повинні видалити поточний вузол:
DELETE FROM DEPARTMENT
WHERE Path LIKE '1 .1% '
За допомогою додаткової точки в аргументі оператора
LIKE можна видалити всі дочірні елементи без батьківського вузла:
DELETE
FROM DEPARTMENT
WHERE
Path LIKE '1 .1 .%'
Має сенс побудувати тригер, який буде
автоматично видаляти дочірні елементи:
CREATE TRIGGER DELETE_NODES_TR
ON DEPARTMENT AFTER DELETE
AS
DECLARE @ ParentPath VARCHAR (180)
BEGIN
SELECT @ ParentPath = Path FROM
deleted
DELETE FROM DEPARTMENT WHERE
Path LIKE @ ParentPath +'.%'
END
У цьому випадку можна гарантувати, що вузол буде
віддалятися разом з дочірніми елементами, і команда видалення ще більше
спроститься.
DELETE
FROM DEPARTMENT WHERE Path = '1 .1 '
Перенесення вузла
Перенесення вузла - більш складна операція, ніж попередня.
Для неї потрібно буде виконати дві команди оновлення. Наприклад, перенесемо вузол
з Path 1.1, зробивши його дочірнім вузлом по відношенню до вузла 1.2. Першою командою
ми перенесемо сам вузол:
UPDATE DEPARTMENT
SET Path =
(SELECT '1 .2. '+
ISNULL (CAST (MAX (D. Position) + 1 AS VARCHAR), '1 ')
FROM DEPARTMENT D
WHERE D. Path LIKE '1 .2.% '
AND D. Path NOT LIKE '1 .2 .%.%'),
Position =
(SELECT ISNULL (MAX (D. Position)
+ 1, '1 ')
FROM DEPARTMENT D
WHERE D. Path LIKE '1 .2.% '
AND D. Path NOT LIKE '1 .2 .%.%')
WHERE Path = '1 .1 '
Другий командою ми відновимо всі ідентифікатори Path для
дочірніх елементів:
UPDATE
DEPARTMENT SET Path = STUFF (Path, 1, 3, '1 .2.4 ')
WHERE
Path LIKE '1 .1 .%'
Так само, як і у випадку з видаленням, ми можемо побудувати
тригер, який буде гарантовано адаптувати дочірні посилання, а також
стежити за правильністю поля Position:
CREATE TRIGGER UPDATE_NODES_TR
ON DEPARTMENT
AFTER UPDATE
AS
DECLARE
@ OldParentPath VARCHAR (180),
@ NewParentPath VARCHAR (180),
@ ParentPosition INT,
@ RealParentPosition INT
BEGIN
IF UPDATE (Path)
BEGIN
SELECT @ OldParentPath = Path
FROM deleted
SELECT @ NewParentPath = Path,
@ ParentPosition = Position FROM inserted
- якщо поле Position некоректно, то оновлюємо його
згідно Path
SELECT @ RealParentPosition =
CAST (RIGHT (@ NewParentPath,
CHARINDEX ('.',
REVERSE (@ NewParentPath)) - 1) AS INT)
IF (@ RealParentPosition
<> @ ParentPosition)
UPDATE DEPARTMENT
SET Position =
@ RealParentPosition
WHERE Path = @ NewParentPath
- оновлюємо всі дочірні елементи
UPDATE DEPARTMENT
SET Path = STUFF (Path, 1,
LEN (@ OldParentPath), @ NewParentPath)
WHERE Path LIKE
@ OldParentPath +'.%'
END
END
Деякі додатки
Одним з корисних властивостей даного алгоритму є
можливість сортувати дані згідно ієрархії. Це дуже корисна і часто
що використовується властивість. Якщо досить часті звернення відповідно до ієрархії, і
якщо дозволяє використовувана СУБД, варто зберігати таблицю в стані,
сортованого по полю Path.
Якщо ви хочете сортувати послідовність
безпосередньо підпорядкованих елементів, то можна ввести додаткову цифру, у
якої буде лежати кількість цифр у елементі. Наприклад, для Position c
номером 2 ідентифікатор у Path буде дорівнює 12, де 1 - кількість символів у
ідентифікаторі. А якщо Position дорівнює 12, то ідентифікатор буде дорівнює 212. У
цьому випадку сортування строкових даних буде збігатися з послідовністю
числових, і ми отримаємо повністю сортованого Path.
Набагато гірше йде справа, якщо потрібно реалізувати
операцію вставки. Якщо адаптувати всі Path на підпорядковані і сусідні вузли.
При цьому втрачається головне достоїнство алгоритму - лінійна швидкість вставки.
Тому, якщо предметна область не вимагає показу класифікатора
користувачам, можна зберігати окремо позиції в послідовності
підлеглих елементів.
У ієрархічного довідника, побудованого за
описаного принципом, як, власне, і у всіх відомих алгоритмів побудови
ієрархій в реляційної системі, є свої недоліки. З його допомогою не можна
створювати ієрархії з дуже великою глибиною. Для таких задач існують інші
алгоритми. Однак для більшості бізнес-додатків він не тільки придатний, але і
володіє такими перевагами, як швидкість роботи і простота використання.
Список літератури
Для підготовки даної роботи були використані
матеріали з сайту http://www.rsdn.ru/
