Основано на докладе nikolay@jetstyle и zharik@jetstyle на семинаре JetStyle, посвященному хранению деревьев в БД (21/01/2005), и дополнена автором. В статье описывается метод хранения деревьев Preordered Tree Traversal, также известный как Nested Sets.

Оглавление статьи

1. Введение
2. Описание метода
3. Преимущества
4. Недостатки
   1. Добавление элемента
   2. Удаление элемента или поддерева
   3. Перемещение элемента или поддерева
   4. Обеспечение целостности
   5. Внимательность при обновлении дерева
5. Дополнительная литература

1. Введение

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

2. Описание метода

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

3. Преимущества

Что нам это дает? Нам это дает то, что выполнение нескольких часто используемых операций по работе с деревом (не связанных с его модификацией) мы можем выполнять за 1 (один) SQL-запрос:

1. Получение поддерева (списка вершин, которые являются поддеревом некой заданной вершины). Для этого нам нужно всего лишь запросить список элементов, левые значения которых больше, чем у заданной вершины, а правые значения - меньше:

   SELECT * FROM `tree` WHERE `left` > {$left} AND `right` < {$right}

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

   SELECT * FROM `tree` WHERE `left` < {$left} AND `right` > {$right} ORDER BY `left` ASC;

3. Получение развернутого списка элементов дерева (обход в глубину).
   Для этого нам нужно просто упорядочить выборку по левому значению:

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

   Совместив это с пунктом 1, можно получить развернутый список некого поддерева.

4. Получение объема поддерева (кол-ва элементов внутри этого поддерева). Для этого нам даже
   дополнительного запроса делать не надо. У вершины, для которой нам нужно получить объем, просто берем (right - left - 1) / 2.
5. Получение общего корня поддерева минимального объема для двух заданных вершин
   можно получить если запросить элемент с наибольшим левым значением (или наименьшим правым), для которого левое значение меньше обоих левых, а правое больше обоих правых:

   $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` > {$parent_left};
UPDATE `tree` SET `right` = `right` + 2 WHERE `right` > {$parent_left};
INSERT INTO `tree` SET `left` = {$parent_left} + 1, `right` = {$parent_left} + 2;

В конец списка:

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

Где $parent_left и $parent_right - это левое и правое значение родительской вершины соответственно.

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

4.2. Удаление элемента или поддерева

Удаление элемента или поддерева тоже относительно просто:

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

Где $left и $right - левое и правое значения вершины удаляемого элемента или поддерева.

4.3. Перемещение элемента или поддерева

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

4.4. Обеспечение целостности

К сожалению, целостность такого дерева легко нарушить и достаточно сложно восстановить. Точнее восстановление состоит в полном пересчете дерева. А нарушить целостность может, например, аварийное прерывание работы, связанной с модификацией структуры дерева. Как было указано выше, добавление и удаление элементов дерева состоит из нескольких запросов. Если выполнить только часть из них, то целостность дерева будет нарушена. Поэтому: во-первых, я настоятельно рекомендую хранить такое дерево в таблице, поддерживающей транзакции (например, InnoDB в MySQL) и производить операции добавления и удаления элементов дерева в рамках транзакции (START TRANSACTION; …; COMMIT;); во-вторых, добавить уникальные индексы на левое и правое значения — это, конечно, не гарантирует целостность, но может помочь предотвратить глупые ошибки при работе с деревом.

4.5. Внимательность при обновлении дерева

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

5. Дополнительная литература

• Storing Hierarchical Data in a Database
• Four ways to work with hierarchical data