Метод зберігання дерев в бд - preordered tree traversal (nested sets)

Зміст статті

1. Введення

При проектуванні бази даних досить часто виникає необхідність в зберіганні дерева, і, оскільки таблиці баз даних спеціально не призначені для зберігання дерев, то доводиться вдаватися до різних трюків. Найпростіший і найочевидніший спосіб - зберігати у кожного елемента
дерева крім ідентифікатора (id) посилання на батьківський елемент (parent_id). Але робота з таким деревом пов'язана з великими накладними витратами, так наприклад, для отримання всього
дерева нам необхідно використовувати рекурсію (або її емуляцію), роблячи по одному SQL-запиту
на кожен елемент дерева. Нижче пропонується опис методу, який дозволяє звести до мінімуму витрати на виконання часто необхідних операцій з деревами.

2. Опис методу

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

Метод зберігання дерев в бд - preordered tree traversal (nested sets)

3. Переваги

Що нам це дає? Нам це дає те, що виконання декількох часто використовуваних операцій по роботі з деревом (не пов'язаних з його модифікацією) ми можемо виконувати за 1 (один) SQL-запит:

  1. Отримання поддерева (списку вершин, які є піддерево якоїсь заданої вершини). Для цього нам потрібно всього лише запросити список елементів, ліві значення яких більше, ніж у заданій вершини, а праві значення - менше:

SELECT * FROM `tree` WHERE `left`> AND `right` <

  • Шлях від кореня. Операція зворотна попередньої - запросити список елементів, ліві значення яких менше, ніж у заданій вершини, а праві значення - більше, і впорядкувати по лівому або правому значенням:

    SELECT * FROM `tree` WHERE `left` ORDER BY `left` ASC;

  • Отримання розгорнутого списку елементів дерева (обхід в глибину).
    Для цього нам потрібно просто впорядкувати вибірку по лівому значенням:

    SELECT * FROM `tree` ORDER BY `left`;

    Поєднавши це з пунктом 1, можна отримати розгорнутий список нікого поддерева.
  • Отримання обсягу поддерева (кол-ва елементів всередині цього піддерева). Для цього нам навіть
    додаткового запиту робити не треба. У вершини, для якої нам потрібно отримати обсяг, просто беремо (right - left - 1) / 2.
  • Отримання спільного кореня піддерева мінімального обсягу для двох заданих вершин
    можна отримати якщо запитати елемент з найбільшим лівим значенням (або найменшим правим), для якого ліве значення менше обох лівих, а праве більше обох правих:

    $ Left = min ($ node1_left, $ node2_left);
    $ Right = max ($ node1_right, $ node2_right);
    SELECT * FROM `tree` WHERE `left` <$left AND ` right `> $ Right ORDER BY `left` DESC LIMIT 1;

    Крім цього, наше дерево володіє деякими можливо корисними властивостями:

    1. Кінцева вершина дерева має ліве значення рівне правому + 1;
    2. Перший нащадок якоїсь вершини має ліве значення рівне лівому значенням батька - 1;
    3. Останній нащадок якоїсь вершини має праве значення рівне правому значенням батька + 1.

    Однак, для рекурсивного обходу дерева, все ж зручніше використовувати більш традиційний метод зберігання дерева з використанням id і parent_id. Не бачу причин відмовлятися від нього - обидва методи зберігання дерева можна з успіхом поєднувати і користуватися таким чином перевагами обох.

    4. Недоліки

    У цього методу є т.зв. downside, який полягає в тому, що при додаванні, видаленні і переміщенні елементів дерева нам необхідно перерахувати заново ліві і праві значення дерева.

    4.1. Додавання елемента

    Додавання нового дочірнього елемента до якоїсь заданої вершині можна виконати двома способами: в початок списку дочірніх елементів і в кінець.

    UPDATE `tree` SET `left` = `left` + 2 WHERE `left`>;
    UPDATE `tree` SET `right` = `right` + 2 WHERE `right`>;
    INSERT INTO `tree` SET `left` = + 1, `right` = + 2;

    UPDATE `tree` SET `left` = `left` + 2 WHERE `left`>;
    UPDATE `tree` SET `right` = `right` + 2 WHERE `right`> =;
    INSERT INTO `tree` SET `left` =, `right` = + 1;

    Де $ parent_left і $ parent_right - це ліве і праве значення батьківської вершини відповідно.

    Додавання відразу декількох елементів в один і той же батьківський елемент може бути оптимізовано: не обов'язково виконувати по 2 апдейта на кожен елемент, - можна виконати 2 апдейта для всіх додаються елементів відразу.

    4.2. Видалення елемента або поддерева

    Видалення елемента або поддерева теж відносно просто:

    DELETE FROM `tree` WHERE `left`> = AND `right` <= ;
    UPDATE `tree` SET `left` = `left` - + - 1 WHERE `left`>;
    UPDATE `tree` SET `right` = `right` - + - 1 WHERE `right`>;

    Де $ left і $ right - ліве і праве значення вершини видаляється елемента або поддерева.

    4.3. Переміщення елемента або поддерева

    Переміщення елемента дерева представляється найбільш важким, в даній операції необхідно перерахувати ліві і праві значення у всього дерева, хоча, можливо, оптимальніше буде реалізувати переміщення через додавання елементів переміщуваного дерева по одному і видалення переміщуваної вершини з усім піддерево.

    4.4. забезпечення цілісності

    На жаль, цілісність такого дерева легко порушити і досить складно відновити. Точніше відновлення полягає в повний перерахунок дерева. А порушити цілісність може, наприклад, аварійне переривання роботи, пов'язаної з модифікацією структури дерева. Як було зазначено вище, додавання і видалення елементів дерева складається з декількох запитів. Якщо виконати тільки частину з них, то цілісність дерева буде порушена. Тому: по-перше, я настійно рекомендую зберігати таке дерево в таблиці, що підтримує транзакції (наприклад, InnoDB в MySQL) і робити операції додавання і видалення елементів дерева в рамках транзакції (START TRANSACTION; ...; COMMIT;); по-друге, додати унікальні індекси на ліве і праве значення - це, звичайно, не гарантує цілісність, але може допомогти запобігти дурні помилки при роботі з деревом.

    4.5. Уважність при оновленні дерева

    При здійсненні модифікації дерева не варто забувати про те, що ліві і праві значення змінюються після кожної зміни структури. Таким чином, якщо ви здійснюєте вибірку елементів дерева з таблиці БД, паралельно з його модифікацією, то ліві і праві значення у вибірці будуть застарілими. Або якщо ви отримали ліве і праве значення і зберегли у відповідних змінних, після модифікації дерева збережені в змінних значення швидше за все будуть застарілими.

    5. Додаткова література

    5 відгуків на "Метод зберігання дерев в БД - Preordered Tree Traversal (Nested Sets)"

    А чи можна зберігати в таблиці при використанні даного методу кілька дерев?

    Або кореневий елемент всього дерева може бути тільки один?

    Можна, більш того, ми взагалі начебто не маємо ніяких засобів забезпечення для списку деревовидної структури, крім, звичайно, власного мозку - ми не контролюємо відсутність циклів і єдиність кореня. Більш того, один і той же вузол може при цьому входити в кілька дерев відразу -но тоді вже виходить "даг". Особисто у мене відразу виникло таке питання - звичайно все це добре, наскільки взагалі можна швидко оперувати з деревами через SQL?

    Залишилося зрозуміти як вивести отформатироване (з відступами) дерево з БД?

    І вважаю, що має бути так:
    - Перший нащадок якоїсь вершини має ліве значення рівне лівому значенням батька + 1; (А не -1)
    - Останній нащадок якоїсь вершини має праве значення рівне правому значенням батька - 1. (а не +1)

    Напишіть що Ви про це думаєте

    Схожі статті