Nested set model е един от многото варианти за съхранение на йерархична структура в релационна база от данни. Както всички останали, и този модел има своите предимства и недостатъци.
Няма перфектен модел по презумпция, по-скоро би могло да се говори за оптимален модел във всеки отделен случай.
При сравняването на различните модели, обикновенно се разглеждат едни и същи сценарии и се търси SQL решението за съответния модел. Обичайни задачи са:
1. Извеждане на цялото дърво.
2. Откриване на всички крайни нива.
3. Откриване на пълния път до определено ниво.
4. Дълбочина на дървото или на избрано под-ниво.
5. Откриване на диреткните под-нива, на избрано ниво.
6. Добавяне на ниво.
7. Изтриване на ниво.
8. Преместване на запис от едно под-дърво в друго.
9. Преместване на едно под-дърво, като част от друго.
Предимствата на nested set model може би се свеждат до прости и бързи заявки при обхождане на дървото (т.1 - т.5). Недостатъците са малко по-сложното добавяне и изтриване на записи (т.6 - т.7) и доста по-трудното преместване на едно под-дърво към друго под-дърво.
Кога е препоръчително да се използва nested set model? Когато много рядко се налага да правим промени по дървото (т.6 - т.9), но пък много често се налага да обхождаме дървото (т. 1 - т. 5).
Примера, който ще разгледам по-долу показва връзките между континент, държава, област, населено място, квартал. Други примери биха могли да бъдат продуктов каталог, родословно дърво, форум с Conversation threading представяне на темите и т.н.
-Континент
--Държава
---Област
----Населено място (град/село)
-----Квартал
Код:
Европа
-България
--Област Пловдив
---Асеновград
----Горни Воден
----Долни Воден
--Област Враца
---Община Бяла Слатина
----с. Соколаре
Северна Америка
-САЩ
--Калифорния
---Лос Анджелис
---Сан Франциско
-Канада
--Онтарио
---Торонто
При описването на всеки запис, се използват индекси, флагове или както искате ги наричайте - ляво и дясно. Първия запис в таблицата би трябвало да има ляво 1 и дясно 2. Втория запис от същото ниво трябва да има ляво 3, дясно 4 и т.н. Когато искате да добавите под-нива, трябва така да променяте числата за ляво и дясно, че да можете да обхождате дървото от ляво на дясно последователно през всички нива. Ето една картинка за пример:
Оракъл са изтрили една много хубава статия от mysql.com, която успях да открия само в сайта на един китайски университет, от там е и картинката:
http://mirror.neu.edu.cn/mysql/tech-resources/articles/hierarchical-data.html
[sql]
CREATE TABLE `area` (
`id` INT(10) UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
`name` VARCHAR(100) NOT NULL,
`lft` INT(10) UNSIGNED NOT NULL,
`rgt` INT(10) UNSIGNED NOT NULL,
KEY `search`(`lft`, `rgt`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
INSERT INTO `area` VALUES
(NULL, 'Европа', 1, 18 ),
(NULL, 'България', 2, 17),
(NULL, 'Област Пловдив', 3, 10),
(NULL, 'Асеновград', 4, 9),
(NULL, 'Горни Воден', 5, 6),
(NULL, 'Долни Воден', 7, 8 ),
(NULL, 'Област Враца', 11, 16),
(NULL, 'Община Бяла Слатина', 12, 15),
(NULL, 'с. Соколаре', 13, 14),
(NULL, 'Северна Америка', 19, 34),
(NULL, 'САЩ', 20, 27),
(NULL, 'Калифорния', 21, 26),
(NULL, 'Лос Анджелис', 22, 23),
(NULL, 'Сан Франциско', 24, 25),
(NULL, 'Канада', 28, 33),
(NULL, 'Онтарио', 29, 32),
(NULL, 'Торонто', 30, 31);
[/sql]
1. Всички под-нива на даден node, например всичко от Европа (1, 18 )
[sql]SELECT * FROM `area` WHERE `lft` > 1 AND `rgt` < 18;[/sql]
2. Откриване на всички крайни нива (т.е. нива, след които няма други под-нива)
[sql]SELECT * FROM `area` WHERE `rgt` = `lft` + 1;[/sql]
3. Взимане на пълния път до определено ниво, например Европа - България - Област Пловдив - Асеновград - кв. Горни Воден (5,6)
[sql]SELECT * FROM `area` WHERE `lft` <= 5 AND `rgt` >= 6;[/sql]
4. Колко под-нива има дадено ниво, например колко записа има под област Пловдив:
[sql]SELECT (`rgt` - `lft` - 1)/2 FROM `area` WHERE `id` = 3;[/sql]
5. Директните (първите) под-нива, на избрано ниво, напр. всички области в България (2, 17), но без населените места (градове, села) и кварталите.
[sql]SELECT `child`.*
FROM `area` AS `child`
LEFT JOIN `area` AS `ancestor` ON
`ancestor`.`lft` BETWEEN 2+1 AND 17-1 AND
`child`.`lft` BETWEEN `ancestor`.`lft`+1 AND `ancestor`.`rgt`-1
WHERE
`child`.`lft` BETWEEN 2+1 AND 17-1 AND
`ancestor`.`id` IS NULL;[/sql]
6. Добавяне на нов запис - още един щат в САЩ - Тексас. Ще бъде добавен от дясно на Калифорния (21, 26), т.е. неговото ляво трябва да е 27, а неговото дясно - да бъде 28. Трябва да направим място - всички, които са след Калифорния, трябва да се преместят с 2 напред - и ляво и дясно.
[sql]
UPDATE `area` SET `rgt` = `rgt` + 2 WHERE `rgt` > 26;
UPDATE `area` SET `lft` = `lft` + 2 WHERE `lft` > 26;
INSERT INTO `area` VALUES (NULL, 'Тексас', 27, 28 );
[/sql]
7. Изтриване на запис - има две ситуации, които трябва да се имат в предвид. Между другото, проблема съществува и при adjacency модела.
7.1. Изтриване на краен запис - например изтриваме Сан Франциско (24, 25)
[sql]
DELETE FROM `area` WHERE `id` = 14;
UPDATE `area` SET `rgt` = `rgt` - 2 WHERE `rgt` > 25;
UPDATE `area` SET `lft` = `lft` - 2 WHERE `lft` > 25;
[/sql]
7.2. Изтриване на запис, който има под-нива, например изтриваме Калифорния. Трябва предварително да решим какво ще правим с осиротелите Лос Анжделис и Сан Франциско (вярно, че примера е за градове и е малко нелогичен, но е реален - до преди няколко години Косово беше област в Сърбия, пък стана самостоятелна държава) - дали някой от тях ще бъде провъзгласено за parent на другото или двете заедно ще бъдат преместени към друго дърво или пък ще бъдат изтрити?
Не искам да разглеждам случайте, при които местим едно под-дърво към друго под-дърво (Калифорния, заедно с градовете си, минава към Мексико), защото и на мен ми е сложно и ще дам подвеждащ SQL код, който не ми е съвсем ясен. Както виждате по-горе, за някой от операциите се изискват няколко заявки. Правете ги в транзакция и разчитайте на rollback, ако има проблеми.
Ако сравняваме с adjacency модела, заявки 2, 3, 4 изискват използването на рекурсивни функции или предварително да се знае дълбочината на дървото и тя да е постоянна за цялата структура. MySQL не поддържа рекурсивни заявки, за разлика от други RDBMS и съответно би трябвало де се пишат рекурсивни РНР или SQL функции.
Предимствата на adjancency модела са лесното управление (5-9), за сметка на трудното обхождане (1-4) на дървото.
