Пользователь
0,0
рейтинг
10 декабря 2008 в 18:18

Разработка → Иерархические структуры данных и Doctrine

Введение



Хранение иерархических данных (или попросту — деревьев) в реляционных структурах задача довольно нетривиальная и вызывает некоторые проблемы, когда разработчики сталкиваются с подобной задачей.

В первую очередь, это связано с тем, что реляционные базы не приспособлены к хранению иерархических структур (как, например, XML-файлы), структура реляционных таблиц представляет из себя простые списки. Иерархические же данные имеют связь «родитель-наследники», которая не реализована в реляционной структуре.

Тем не менее, задача «хранить деревья в базе данных» рано или поздно возникает перед любым разработчиком.

Ниже мы подробно рассмотрим, какие существуют подходы в организации хранения деревьев в реляционных БД, а также рассмотрим инструментарий, который нам предоставляет ORM Doctrine для работы с такими структурами.

Список смежных вершин (Adjacency List)



Описание структуры



Как правило, такая структура данных предполагает хранение информации о смежных вершинах нашего дерева. Давайте рассмотрим простейший граф с темя вершинами (1,2,3):



Рис. 1. Граф с тремя вершинами

Как видим каждый элемент данного графа хранит информацию о связи с другими элементами, т.е.:

1 - 2,3
2 - 1,3
3 - 1,2


Фактически, для построения дерева такой граф избыточен, т.к. для привычной ветвистой структуры нам нужно хранить только связь «родитель-наследник», т.е.:

2-1
3-1


Тогда мы получим дерево с одним корневым элементом (1) и двумя ветками (2,3):



Рис. 2. Граф дерева

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

Итак, чтобы хранить в базе данных иерархическую структуру методом списка смежных вершин (Adjacency List), нам необходимо хранить информацию о связях «наследник-родитель» в таблицах с данными. Давайте рассмотрим реальный пример дерева:



Рис. 3. Древовидная структура методом смежных вершин

На рисунке квадратами обозначены узлы деревьев. У каждого узла есть имя (верхний прямоугольник внутри квадрата), идентификатор (левый нижний квадрат) и ссылка на идентификатор родителя (правый нижний квадрат). Как видно из Рис. 3, каждый наследник в такой структуре ссылается на своего предка. В терминах БД мы можем это отобразить следующим образом в виде таблицы:



Рис. 4. Таблица данных дерева, построенная методом списка смежных вершин

Или же в виде SQL:

CREATE TABLE al_tree (
    `id` BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
    `parent_id` BIGINT NULL,
    `name` VARCHAR(50) NOT NULL
) TYPE=InnoDB DEFAULT CHARSET=utf8;

CREATE INDEX fk_tree_tree ON al_tree (parent_id);

ALTER TABLE al_tree ADD CONSTRAINT fk_tree_tree
    FOREIGN KEY (parent_id) REFERENCES al_tree (id) ON UPDATE CASCADE ON DELETE CASCADE;

INSERT INTO al_tree VALUES
    (1, NULL, 'FOOD'),
    (2, 1, 'VEGETABLE'),
    (3, 2, 'POTATO'),
    (4, 2, 'TOMATO'),
    (5, 1, 'FRUIT'),
    (6, 5, 'APPLE'),
    (7, 5, 'BANANA');


Следует сразу отметить, что такой алгоритм хранения деревьев обладает определенными как достоинствами, так и недостатками. В первую очередь, он не совсем удобен для чтения — и это его основной недостаток.

Проблемы с чтением из БД менее заметны, если вычитывать все дерево целиком. Это достаточно простой запрос:

SELECT * FROM al_tree ORDER BY id;


Результат:

+----+-----------+-----------+
| id | parent_id | name      |
+----+-----------+-----------+
|  1 |      NULL | FOOD      |
|  2 |         1 | VEGETABLE |
|  3 |         2 | POTATO    |
|  4 |         2 | TOMATO    |
|  5 |         1 | FRUIT     |
|  6 |         5 | APPLE     |
|  7 |         5 | BANANA    |
+----+-----------+-----------+


Однако в дальнейшем такая выборка подразумевает достаточно емкую программную пост-обработку данных. Сначала нужно рекурсивно перестроить данные с учетом связей «предок-наследник» и лишь потом их можно будет использовать для вывода куда-либо.

Другой вариант чтения дерева целиком:

SELECT t1.name AS lvl1, t2.name as lvl2, t3.name as lvl3
FROM al_tree AS t1
LEFT JOIN al_tree AS t2 ON t2.parent_id = t1.id
LEFT JOIN al_tree AS t3 ON t3.parent_id = t2.id
LEFT JOIN al_tree AS t4 ON t4.parent_id = t3.id
WHERE t1.id = 1;


Результат в данном случае будет такой:

+------+-----------+--------+
| lvl1 | lvl2      | lvl3   |
+------+-----------+--------+
| FOOD | VEGETABLE | POTATO |
| FOOD | VEGETABLE | TOMATO |
| FOOD | FRUIT     | APPLE  |
| FOOD | FRUIT     | BANANA |
+------+-----------+--------+


Хотя данные в таком виде уже более приспособлены сразу для вывода, но, как видите, главный недостаток такого подхода — необходимо достоверно знать количество уровней вложенности в вашей иерархии, кроме того, чем больше иерархия, тем больше JOIN'ов — тем ниже производительность.

Тем не менее, данный способ обладает и существенными достоинствами — в дерево легко вносить изменения, менять местами и удалять узлы.

Вывод — данный алгоритм хорошо применим, если вы оперируете с небольшими древовидными структурами, которые часто поддаются изменениям.

С другой стороны, этот алгоритм также довольно уверенно себя чувствует и с большими деревьями, если считывать их порциями вида «знаю родителя — прочитать всех наследников». Хороший пример такого случая — динамически подгружаемые деревья. В этом случае алгоритм практически оптимизирован для такого поведения.

Однако он плохо применим, когда нужно вычитывать какие-либо иные куски дерева, находить пути, предыдущие и следующие узлы при обходе и вычитывать ветки дерева целиком (на всю глубину).

Использование списка смежных вершин в Doctrine



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

Итак, сущности, которыми мы оперируем в ORM Doctrine — это активные записи (Active Record). Т.е. объекты, которые совмещают в себе бизнес-логику и сами умеют взаимодействовать с базой данных. Но разработчики Doctrine предусмотрели расширение функциональности объектов записей не только наследованием, но и применением к этим объектам «шаблонов поведения». Это реализуется пакетом Doctrine/Template.

Т.о., если возникает необходимость воспитать активную запись до какого-либо поведения (например, Versionable — проводит аудит всех изменений, I18N — многоязычная или NestedSet — древовидная вида «вложенное множество»), то это можно сделать как раз с помощью данных шаблонов поведения.

Чтобы подключить какой-либо из существующих шаблонов, достаточно сконфигурировать должным образом нашу модель (посредством YAML или прямо в коде базовой таблицы модели).

Когда придет время, мы покажем на примерах, как это сделать.

Пока, к сожалению, или к счастью, но в виде шаблона к таблицам метод списка смежных вершин в Doctrine не реализован. При желании вы можете написать реализацию сами и даже предложить ее разработчикам Doctrine, — это уже на ваше усмотрение.

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

Для этого следует сконфигурировать нашу модель должным образом. Используя YAML опишем структуру нашей таблицы:

AlTree:
  tableName: al_tree
  columns:
    id:
      type: integer(8)
      primary: true
      autoincrement: true
    name:
      type: string(50)
      notnull: true
    parent_id: integer(8)


А вот теперь самое важное — правильно описать связи в таблице. Там же со следующей строчки напишем:

  relations:
    Parent:
      class: AlTree
      local: parent_id
      foreign: id
      type: one
    Children:
      class: AlTree
      local: id
      foreign: parent_id
      type: many


Теперь соберем нашу модель, запустив команду:

./doctrine generate-models-yaml


Все. Модель готова. Фактически тоже самое можно было сделать в уже готовом базовом классе BaseAlTree:

<?php
...
  public function setUp()
  {
    $this->hasOne('AlTree as Parent', array('local' => 'parent_id',
                                            'foreign' => 'id'));

    $this->hasMany('AlTree as Children', array('local' => 'id',
                                               'foreign' => 'parent_id'));
  }
...
?>


Теперь пришло время насладиться результатами нашей работы. Напишем несложный код, отображающий дерево, построенное с отступами на обычной HTML-странице, используя рекурсию.

<?
/**
 * Извлекаем корневой элемент дерева
 */
$root = Doctrine::getTable( 'AlTree')->findByDql( 'WHERE parent_id IS NULL')->getFirst();
echo '<pre>';
printRTree( $root);
echo '</pre>';

/**
 * Рекурсивно печатет дерево на экран
 *
 * @param AlTree $node - объект записи - узел дерева
 * @param int $level - уровень вложенности переданого узла
 */
function printRTree( AlTree $node, $level = 0) {
	/**
	 * Вот эта строчка и "рисует" наше дерево
	 */
	echo str_repeat( "\t", $level) . $node->getName() . "\n";

	/**
	 * Далее проверяем, есть ли наследники,
	 * и если есть - входим в рекурсию.
	 * Обратите внимание - вот то чудо-свойство
	 * Children, которое мы описали в конфиге
	 * нашей модели!
	 */
	if (($children = $node->Children->getIterator()) && $children->count() > 0) {
		$level++;
		while (($child = $children->current())) {
			/**
			 * Входим в рекурсию
			 */
			printRTree( $child, $level);
			$children->next();
		}
	}
}
?>


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

Но в тоже время, реализовать динамически подгружаемое дерево таким способом — одно удовольствие!

Вложенное множество (Nested Set)



Описание структуры



Об этом алгоритме и его быстродействии, наверное, слышали все веб-разработчики. Да, этот алгоритм действительно очень хорош, когда требуется часто и много обращаться к иерархическим данным на чтение. Рассмотрим суть данного подхода.

При построении дерева на основе вложенных множеств, мы воспользуемся принципом обхода этого дерева слева-направо, как показано стрелками на Рис. 5. Для этого определим для каждого узла дерева целочисленные ключи слева (lft) и справа (rgt) (нижние квадратики внутри узла). И раздадим им во время обхода целочисленные инкрементные значения. Посмотрите что получилось.



Рис. 5. Вложенное множество (Nested Set).

Корневой элемент получил ключи 1 и 14, которые включают в себя диапазон чисел всех остальных ключей. Ветка VEGETABLE получила ключи 2 и 7, которые, в свою очередь, включают весь диапазон чисел ключей всех ее наследников и т.д. Вот они — вложенные множества. Все просто, не так ли?

Давайте воссоздадим такую же структуру в контексте таблицы БД.



Рис. 6. Таблица иерархических данных на основе метода вложенных множеств

Или же в виде SQL:

CREATE TABLE ns_tree (
    `id` BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
    `name` VARCHAR(50) NOT NULL,
    `lft` BIGINT NOT NULL,
    `rgt` BIGINT NOT NULL,
    `level` BIGINT NOT NULL
) TYPE=InnoDB DEFAULT CHARSET=utf8;

CREATE INDEX nslrl_idx ON ns_tree (lft, rgt, level);

INSERT INTO ns_tree VALUES
    (1, 'FOOD', 1, 14, 0),
    (2, 'VEGETABLE', 2, 7, 1),
    (3, 'POTATO', 3, 4, 2),
    (4, 'TOMATO', 5, 6, 2),
    (5, 'FRUIT', 8, 13, 1),
    (6, 'APPLE', 9, 10, 2),
    (7, 'BANANA', 11, 12, 2);


Как видите, мы ввели дополнительно еще одно поле в таблицу — level. В нем будет храниться информация об уровне вложенности каждой ветки дерева. В принципе, это делать вовсе не обязательно — уровень вложенности может быть достаточно просто вычислен, но так как данный алгоритм оптимизирован как раз для чтения, то почему бы не выиграть в производительности за счет кеширования информации об уровне? Риторический вопрос…

Чтение дерева из БД

Читаем все дерево:

SELECT node.id, node.name, node.level
FROM ns_tree AS node,
ns_tree AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND parent.id = 1
ORDER BY node.lft;


Результат будет таким:

+----+-----------+-------+
| id | name      | level |
+----+-----------+-------+
|  1 | FOOD      |     0 |
|  2 | VEGETABLE |     1 |
|  3 | POTATO    |     2 |
|  4 | TOMATO    |     2 |
|  5 | FRUIT     |     1 |
|  6 | APPLE     |     2 |
|  7 | BANANA    |     2 |
+----+-----------+-------+


Теоретически, тот же результат мы бы могли получить, вычисляя уровень вложенности на лету:

SELECT node.id, node.name, (COUNT(parent.id) - 1) AS level
FROM ns_tree AS node,
ns_tree AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;


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

Таким же, довольно несложным образом мы можем считывать целые ветки, пути из нашего дерева, обходить его узлы и т.д.

Например, если мы хотим извлечь все овощи (VEGETABLE) из нашего примера, это сделать достаточно просто:

SELECT node.id, node.name, node.level
FROM ns_tree AS node, ns_tree AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt AND parent.id = 2
ORDER BY node.lft;


При этом, если необходимо исключить из результатов самого родителя вы можете поступить несколькими методами:
  • добавив HAVING level > 1
  • добавив в условие WHERE: AND node.id != 2

или другим способом — пусть это будет творческой задачей для читателя.

Да, быстрое и гибкое чтение, включая агрегацию с внешними связанными данными — конек данного алгоритма.

Тем не менее, не бывает худа без добра, и в данном случае, значительные трудности начинаются когда нам необходимо внести изменения в Nested Set дерево или удалить какую-либо из его ветвей.

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

Смотрите сами.

Добавление новой ветки

Предположим, что мы хотим добавить новую ветку с именем SEA FOOD в наше дерево на одном уровне с VEGETABLES и FRUIT.

BEGIN;

SELECT @treeRight := rgt FROM ns_tree
WHERE id = 2; /* справа от ветки VEGETABLES, у которой id = 2 */

UPDATE ns_tree SET rgt = rgt + 2 WHERE rgt > @treeRight;
UPDATE ns_tree SET lft = lft + 2 WHERE lft > @treeRight;

INSERT INTO ns_tree VALUES(0, 'SEA FOOD', @treeRight + 1, @treeRight + 2, 1);

COMMIT;


Если вы используете в MySQL таблицы MYISAM, или версию, которая не поддерживает транзакции, вы можете вместо BEGIN и COMMIT использовать блокировки на запись:

LOCK TABLE ns_tree WRITE;
...
UNLOCK TABLES;


Как видите, задача на добавление новой ветки достаточно затратная и нетривиальная. Тем не менее, решаемая.

Удаление ветки

Давайте теперь попробуем удалить вновь созданную ветку:

BEGIN;

SELECT @treeLeft := lft, @treeRight := rgt, @treeWidth := rgt - lft + 1
FROM ns_tree
WHERE id = 8; /* здесь идентификатор новой записи с именем 'SEA FOOD' */

DELETE FROM ns_tree WHERE lft BETWEEN @treeLeft AND @treeRight;
/*
  ВНИМАНИЕ!
  Обратите внимание - мы не удаляем по id,
  Хотя в данном случае это бы нас устроило.
  Но в общем случае нам необходимо удалить всю ветку с ее содержимым!
*/

UPDATE ns_tree SET rgt = rgt - @treeWidth WHERE rgt > @treeRight;
UPDATE ns_tree SET lft = lft - @treeWidth WHERE lft > @treeRight;

COMMIT;


Вывод — Nested Set действительно хорош, когда нам необходимо считывать структуру деревьев из БД. При этом он одинаково хорош для деревьев любого объема.

Тем не менее, для иерархических структур, которые подвергаются частому изменению он, очевидно, не будет являться оптимальным выбором.

Использование Nested Set в Doctrine



А вот этот метод имеет отражение в Doctrine в виде реализации шаблона поведения, который мы можем привязать к нашей модели.

Сделать это довольно просто, методом конфигурации модели через YAML-конфиг или прамо в коде базового класса.

YAML:

NsTree:
  tableName: ns_tree
  actAs: [NestedSet]
  columns:
    id:
      type: integer(8)
      primary: true
      autoincrement: true
    name:
      type: string(50)
      notnull: true
    lft:
      type: integer(8)
      notnull: true
    rgt:
      type: integer(8)
      notnull: true
    level:
      type: integer(8)
      notnull: true


Как видите, достаточно просто указать actAs: [NestedSet] в описании класса.

Однако Doctrine предоставляет более гибкую конфигурацию NestedSet модели. Например, вы можете хранить в одной таблице несколько деревьев. Для этого, вам необходимо ввести в таблицу дополнительное поле, в котором вы будете хранить идентификатор корня дерева для каждой записи.

В этом случае конфигурацию следовало бы записать так:

NsTree:
  tableName: ns_tree
  actAs: 
    NestedSet:
      hasManyRoots: true
      rootColumnName: root_id
  columns:
    id:
      type: integer(8)
      primary: true
      autoincrement: true
    root_id:
      type: integer(8)
      notnull: true
    name:
      type: string(50)
      notnull: true
    lft:
      type: integer(8)
      notnull: true
    rgt:
      type: integer(8)
      notnull: true
    level:
      type: integer(8)
      notnull: true


Все то же самое могло бы быть проделано в существующем базовом классе модели.

Для первого случая:

<?php
...
    public function setTableDefinition()
    {
        ...
        $this->actAs('NestedSet');
       ...
    }
...
?>


или:

<?php
...
    public function setTableDefinition()
    {
        ...
        $this->actAs('Doctrine_Template_NestedSet');
       ...
    }
...
?>


Для второго случая (несколько деревьев):

<?php
...
    public function setTableDefinition()
    {
        ...
        $options = array('hasManyRoots'     => true,
                         'rootColumnName'   => 'root_id');
        $this->actAs('NestedSet', $options);
       ...
    }
...
?>


Заметьте, Doctrine использует 'root_id' в качестве имени поля по умолчанию. Поэтому вам не обязательно указывать эту опцию, если оно совпадает с именем в вашей реальной таблице. В противном случае вы можете его задать.

Примеры работы с деревьями Nested Set в Doctrine

Извлекаем и печатаем все дерево на экран:

<?php
$tree = Doctrine::getTable( 'NsTree')->getTree()->fetchTree();
echo "<pre>";
foreach ($tree as $node) {
    echo str_repeat( "\t", $node['level']) . $node['name'] . "\n";
}
echo "</pre>";
?>


Посмотрите как это просто!

За дополнительными примерами и информацией вы можете обратиться к официальной документации Doctrine, разделы 8.2.4 и 8.2.5

Материализованный путь (Materialized Path)



Описание структуры



Еще один довольно интересный подход для хранения иерархических структур. Основная идея алгоритма в хранении полного пути к узлу от вершины дерева. Выглядит это примерно так:



Рис. 7. Древовидная структура, организованная по принципу «материализованый путь»

Принцип формирования таких путей достаточно прост. Глубина пути — это уровень дерева. Внутри ветки нумерация — инкрементная. Другими словами, VEGETABLE — первый ребенок FOOD, FRUIT — второй ребенок и т.д.

Проще будет взглянуть на это в виде таблицы:

+---------------+-------+
| name          | path  |
+---------------+-------+
| FOOD          | 1     |
|   VEGETABLE   | 1.1   |
|     POTATO    | 1.1.1 |
|     TOMATO    | 1.1.2 |
|   FRUIT       | 1.2   |
|     APPLE     | 1.2.1 |
|     BANANA    | 1.2.2 |
+---------------+-------+


Возможно, так даже более наглядно.

В базе данных все это находит следующее отражение.



Рис. 8. структура таблицы иерархических данных, организованных по принципу «материализованный путь»

Или в виде SQL:

CREATE TABLE mp_tree (
    `id` BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
    `name` VARCHAR(50) NOT NULL,
    `path` VARCHAR(100) NOT NULL
) TYPE=InnoDB DEFAULT CHARSET=utf8;

CREATE INDEX mpp_idx ON mp_tree (`path`);

INSERT INTO mp_tree VALUES
    (1, 'FOOD', '1'),
    (2, 'VEGETABLE', '1.1'),
    (3, 'POTATO', '1.1.1'),
    (4, 'TOMATO', '1.1.2'),
    (5, 'FRUIT', '1.2'),
    (6, 'APPLE', '1.2.1'),
    (7, 'BANANA', '1.2.2');


В чем же преимущество такого подхода?

Во-первых, по сравнению с Nested Set, он более поддается изменениям. В то же время остается достаточно удобным для выборки деревьев целиком и их частей. Но, и он не идеален. Особенно по части поиска предков ветки.

Поиск пути к узлу:

SELECT t1.name from mp_tree t1, mp_tree t2
WHERE t2.path like CONCAT( t1.path, '.%')
AND t2.id = 3; /* Поиск пути к узлу с именем 'POTATO' */


Результат:

+-----------+
| name      |
+-----------+
| FOOD      |
| VEGETABLE |
+-----------+


Вычисление уровня вложенности.

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

CREATE FUNCTION STRFIND (str VARCHAR(255), delimtr CHAR(1)) RETURNS INT
BEGIN
DECLARE _cnt INT;
DECLARE _start INT;
SET _cnt = -1;
SET _start = 1;
WHILE _start > 0 DO
  SET _start = LOCATE( delimtr, str);
  SET str    = SUBSTRING( str, _start + 1);
  SET _cnt   = _cnt + 1;
END WHILE;
RETURN _cnt;
END


Выбор ветки:

SELECT name, strfind( path, '.') AS level 
FROM mp_tree 
WHERE path LIKE '1.1%'; /* Выбираем всю ветку 'VEGETABLES' */;


Результат:

+-----------+-------+
| name      | level |
+-----------+-------+
| VEGETABLE |     1 |
| POTATO    |     2 |
| TOMATO    |     2 |
+-----------+-------+


Обратите внимание, в данном примере мы воспользовались нашей самописной функцией и это было достаточно удобно.

Поиск родителя:

SELECT t2.* 
FROM mp_tree t1, mp_tree t2 
WHERE t1.id=3 AND t2.path=SUBSTRING( t1.path, 1, (LENGTH(t1.path) - LOCATE('.', REVERSE(t1.path))));


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

Насколько известно автору, алгоритм довольно уверенно себя чувствует на достаточно больших объемах данных.

Следует отметить, что наиболее неприятной в данном алгоритме будет операция вставки узла в середину уже существующей структуры (между другими узлами), т.к. это повлечет изменение всех путей в нижележащих узлах. Хотя, справедливости ради, следует сказать, что такая операция окажется нетривиальной для любой модели хранения данных. Другая тяжелая операция — это перенос одной ветки в другую.

А вот удаление, добавление в конец или изменение узла — это операции довольно простые, и, как правило, не вызывают сложностей в данной модели.

Как видно из примеров, данный алгоритм также можно несколько оптимизировать на чтение, путем введения ещё одного поля level, как это было сделано для списков смежных вершин (Nested Set). Однако это несколько усложнит операции добавления, изменения и удаления узлов дерева, т.к. уровни придется пересчитывать для всего или части дерева при каждом изменении. В конечном счете, именно разработчику решать, в какую сторону следует делать перекос производительности.

Использование в Doctrine



К сожалению, на данный момент, этот метод хранения деревьев пока не нашел своей реализации в ORM Doctrine (текущая версия на момент написания материала — 1.0.4, 1.1.0 — в альфа версии также реализации не имеет).

Тем не менее есть все предпосылки полагать, что его реализация появится в будущем, т.к. исходные коды библиотеки содержат в пакете Doctrine/Tree абстракный пустой класс с именем MaterializedPath.

Автор будет следить за событиями и обновит эту статью, как только реализация найдет свое отражение, так что можете сюда вернуться позже.

Комбинированный подход



По сути вопроса следует отметить, что скомбинировать приведенные методы можно лишь в двух направлениях:
  • Списки смежности + материализованный путь (Adjacency List + Materialized Path)
  • Списки смежности + вложенные множества (Adjacency List + Nested Set)

Комбинировать же Nested Set и Materialized Path особого смысла не имеет, т.к. существенного выигрыша ни в чтении, ни в записи вы не получите.

Фактически, комбинирование подходов на уровне БД ограничивается вводом поля, хранящего ссылку на родительскую запись в таблицы списков смежности и материализованных путей:



Рис. 9. Таблицы моделей иерархических структур данных AL+MP и AL+NS

Последствия такого подхода очевидны.

AL+MP

Для AL при использовании с MP:
  • Улучшаются операции выборки ветвей и поддеревьев целиком
  • Ухудшаются операции переноса ветвей


Для MP при использовании с AL:
  • Улучшаются операции выборки родителей заданного узла
  • Улучшаются операции выборки наследников заданного узла


AL+NS

Для связки AL+NS взаимовыгодность не столь очевидна. В первую очередь это объясняется тем, что недостатки от проблем изменения узлов дерева в модели NS напрочь убивают в этой сфере все достоинства AL. Это значит, что такую связку следует рассматривать лишь как качественное улучшение поиска родителей и наследников заданного узла в алгоритме NS, а также как повышение надежности самого алгоритма (ключи можно всегда перестроить в случае порчи — информацию о связях хранит AL). Утверждение о повышении надежности справедливо и для предыдущей комбинации методов. Но ведь и это качественное улучшение, хотя и не такое очевидное, не так ли?

Заключение



В данной статье мы рассмотрели несколько основных методов хранения иерархических данных в реляционных БД и очертили все их достоинства и недостатки. Также мы показали на практике, какие из них доступны для использования в реализации ORM Doctrine, и как их использовать.

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

Удачи в девелопменте!

P.S. Это кросс-пост оригинальной статьи с моего блога
Михаил Стадник @Mikhus
карма
115,7
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (41)

  • +3
    Неплохая статья. Хотя местами расходится с фактами.
    Хотя данные в таком виде уже более приспособлены сразу для вывода, но, как видите, главный недостаток такого подхода — необходимо достоверно знать количество уровней вложенности в вашей иерархии, кроме того, чем больше иерархия, тем больше JOIN'ов — тем ниже производительность.
    (про JOIN и про Adjacency List).
    Там проблема скорее в ограничении количества таблиц, которые можно JOINуть. У Котерова был эксперимент — на ограничении 32 таблицы запрос по выборке дерева большого и сильно вложенного (уровень вложенности 8) с 32 JOINами работает (можно найти на dklab — проверял месяца три назад) примерно с той же скоростью, что и 8 JOINов (примерно с той же скоростью в данном случае означает флуктуации между запросами на уровне флуктуации скорости выполнения одного запроса)

    NESTED SETS, если его попробовать (у меня ощущение, что про него пишут просто потому что он упоминается в любой статье про деревья) реально применить, годится либо для деревьев, которые никогда не будут меняться и данные в которые никогда не будут дописываться в середину дерева, либо для «кустиков» до 800 узлов суммарно. Потому как при больших (ударение на первую букву) размерах, вставка узла в середину начинает занимать около МИНУТЫ на не самом отстойном железе и внятно сконфигуренной базой. У Nested Sets имеется один единственный замечательный + — вывод дерева в правильном порядке.

    Materialized Path в классическом виде хранит информацию о предках, а не порядок вывода по отношению к предкам. Если скомбинировать классический Materialized Path с Materialized Path, приведенным в этом примере, да еще написать правильную функцию сравнения того Materialized Path, в котором порядок вывода хранится, получится вполне внятное дерево, выводимое единым запросом в правильном порядке. Правда, остаются проблемы с переносом веток, но, проблемы эти решаются (т.е. перенос ветки с вложенностью 5 и 7000 потомков занимает, в среднем, около 2 секунд совместной работы PostgreSQL+PHP).

    А в целом, хотелось бы в таких статьях (это вроде как уже не первая) побольше конкретики собственного опыта (я вырастил дерево такой-то вышины и такой-то ширины, и храню я это дерево там-то и там-то потому-тои потому-то)
    • +1
      «Потому как при больших (ударение на первую букву) размерах, вставка узла в середину начинает занимать около МИНУТЫ на не самом отстойном железе и внятно сконфигуренной базой.»

      Вставка в дерево в ~700 узлов занимала от 2 до 4 секунд до переделки запроса на batch (bulk) update. После такой переделки изменение дерева в ~1300 (это ведь больше 800?) узлов никогда не занимала больше 1-1.2 секунды. Oracle, p4 несколько лет назад (т.е. максимум, что там было — HT, никаких Quad Core). От работы с nested sets на PostgreSQL впечатления аналогичные.

      Я затрудняюсь представить себе, что нужно сделать c подобными запросами, чтобы обновление заняло минуту.
      • 0
        Еще раз. Есть дерево. ветвистое. глубокое. Суммарно — около 100000 узлов, вложенность что-то порядка 15. Начинаем формировать дерево Nested Sets из имеющегося Adjacency List. Поскольку работа с деревом предполагает, в том числе, копирование, перемещение веток, а также вставку узлов в середину, данные перед вставкой берутся в сравнительно произвольном порядке. До 500 узлов тормозов не заметно, после начинаются нарастающие тормоза. Начиная с 700 узлов среднее время выполнения вставки составляет около минуты на узел. После вставки 1300 узлов процесс остановлен.
        Опыт проводился на тестовом сервере (Athlon 2500XP) и на PostgreSQL 8.3. Для чистоты эксперимента был проведен раза три, с вариациями по порядку выборки исходного дерева. Существенных изменений в производительности не замечалось.
        Железка, когда еще была боевым сервером, держала сайты суммарной посещаемостью около 800000 хитов в сутки + почту к этим сайтам и испытывала проблемы разве что от кривоватых рук тогдашнего админа (сволочь ротацию логов как-то совсем криво делал).
        А с самими запросами ничего не делалось. просто вставлялся узел, потом апдейтилось дерево.
        • 0
          Туше. Но, простите, но из Ваших слов о nested set (и более ранних) никак не следовало, что в дереве 100000 узлов.

          А с самими запросами ничего не делалось. просто вставлялся узел, потом апдейтилось дерево
          Сложно что-то предлагать, не зная деталей, но я бы начал с упрощения операции вставки. Никто же не заставляет значения leftBound и rightBound быть строго последовательными — создавайте их с шагом хоть в 10000, тогда вставка и перемещение узлов будут приводить к пересчёту дерева гораздо реже (хотя «балансировку» время от времени выполнять придётся, конечно), новые узлы будут просто укладываться в резерв родительского диапазона.

          Кстати, не поделитесь — что это за предметная область такая, что надо постоянно перемещать участки иерархии и добавлять новые кусты больших размеров?
          • 0
            Так когда мы пытались сформировать дерево в nested sets, оно там никогда выше 1300 — 1400 узлов не дорастало))). мы скрипт отрубали.
            делать границы с шагом, разумеется, можно, но не универсально — а мы пытались выработать некий универсальный подход, который позволил бы нам работать с большими деревьями быстро и с минимальными затратами.
            А предметная область удручающе банальна — web-дизайн. Мы используем дерево в качестве универсального хранилища данных для сайта/группы сайтов. Там, не то, чтобы постоянно, но регулярно возникают задачи по копированию/перемещению/вставке в середину иногда одиночных узлов, а иногда весьма ветвистых веток. Фактически, любое обновление сайта означает вставку одиночного узла, а если на сайте болтается какой-нить мультитоварный каталог посерьезнее — возникает необходимость делать вставки участков иерархии. Nested Sets для решения наших задач не подошло совсем — слишком много в общем случае объектов на update. Причем количество этих объектов, вообще говоря, не контролируется.
            Это как с рекурсией. Рекурсия по дереву сверху вниз есть абсолютное зло, поскольку, находясь наверху, мы не можем оценить количество рекурсивных вызовов. С другой строны, рекурсия снизу вверх, при определенных обстоятельствах, вполне допустима — поскольку количество вызовов ограничено вложенностью начального узла.
    • 0
      Согласен.
      Кроме того, автор передергивает:
      наиболее неприятной в данном алгоритме будет операция вставки узла в середину уже существующей структуры (между другими узлами), т.к. это повлечет изменение всех путей в нижележащих узлах. Хотя, справедливости ради, следует сказать, что такая операция окажется нетривиальной для любой модели хранения данных.

      тут нужно было бы продолжить: «… для любой модели кроме классики смежных вершин (которая, на практике и является верным выбором фактически всегда).».
      Другая тяжелая операция — это перенос одной ветки в другую.

      Аналогично-с.
  • НЛО прилетело и опубликовало эту надпись здесь
  • +3
    эх, люблю Oracle… :)

    SELECT id, parent_id, name
    FROM al_tree
    START WITH parent_id = NULL
    CONNECT BY PRIOR id = parent_id;

    • +1
      Эх, как я и сам это люблю. :) Единственный недостаток — так редко удается с ним работать!
      • 0
        Мне кажется, это вам так намекают, что примеры лучше было бы оформлять на более или менее «чистом» SQL, без платформозависимых конструкций! _)
    • +1
      так, а минус за "= NULL" вместо «IS NULL», или просто так, от доброго сердца? :)
    • НЛО прилетело и опубликовало эту надпись здесь
      • +1
        Да делаейте что хотите, кто вам запрещает? :)
    • 0
      А я люблю MS SQL — там есть конструкция WITH которая сводит всю эту статью к одному такому же короткому запросу и даже лучше чем в Оракле :-)

      Пользуюсь ей уже два года, работаю с ней постоянно, рад что могу делать простые таблицы (id, parentid) и не городить таких сложных велосипедов как описано в этой статье.
  • –1
    На мой взгляд, статья была бы отличной и без упоминания о Doctrine.
    • +1
      А чем вам не нравится данная orm?
  • 0
    Спасибо. Очень познавательно.
  • –1
    Мелкие замечания. Как раз изучаю теорию графов, и вот — случай блеснуть знаниями =).
    Не совсем понятно, почему автор выкинул из графа именно нижнее ребро (т. е. почему автор решил выбрать корнем дерева именно вершину 1) — получается совершенно другой граф. Речь, видимо, идет о покрывающих деревьях графа, то с тем же успехом можно было выкинуть любое другое ребро — получили бы три разных покрывающих дерева.
    Если же автор выбрал его произвольно — то об этом стоит написать.
    Далее, связи между вершинами правильнее писать через отображения:
    Г(1) = {2,3};
    Г(2) = {1,3};
    Г(3) = {1,2}.

    По теме, собственно первый комментатор высказался исчерпывающе.
    • 0
      потому что дерево и граф — все-таки немного разны понятия. Графы в WEB (а иначе откуда берется мускуль, в отличие от деревьев, не юзаются). Для графа нужна совсем другая структура данных. по собственному опыту — мерзотная.
      • +1
        > потому что дерево и граф — все-таки немного разны понятия

        Дерево есть неориентированный связный граф без циклов. А не «немного разные понятия».

        > графы в WEB (а иначе откуда берется мускуль), в отличие от деревьев, не юзаются.

        *FIXED*
        Откуда такая безапелляционность?

        > Для графа нужна совсем другая структура данных.

        Ты просто специализируешь конкретную структуру на данном виде графа.

        > по собственному опыту — мерзотная.

        Структура графа совершенно спокойно хранится в виде матриц смежности и инцедентности — идеальная форма для обработки компьютером.

      • 0
        деревья — это подмножество графов
        графы юзаются в программировании с самого начала — блок-схемы например :)
        Еще UML, BPEL, правда для их описания используется XML, суть которого — дерево :)
  • +1
    Статья очень неплохая.
    Вы немного не правы насчет «смеси» NS + материализованный путь.
    Если «заваливаться» в сторону NS — то выиграша никакого, но если завалиться в сторону МП — то получится очень быстрая смесь ;)
    Получается почти идеальный алгоритм :) Почему почти? Появляется избыточность данных. Но совсем небольшая.
    Очень легко получать родителей, детей. Выборка без всяких join. Никаких liкe% concat и т.п.
    Многие коммерческие продукты пользуются этим алгоритмом. Видел у IBM например.
    • +1
      Точнее я бы сказал смесь AL+NS+МП :)
      • +1
        Это другое дело, только NS+MP, как мне кажется, неэффективен :)
        • 0
          Даже скорее так МП+AL+NS в таком порядке, причем от NS только логика :)
    • 0
      Да я согласен с вами. Достаточно немного «прокачать» MP и всё будет тоже довольно быстро — например автор позволил себе в NS закешировать левел — ради бога, кешируйте его и в MP (почему нет?) — это сильно развяжет вам руки! Можно простыми запросами дёргать определённые уровни, детей и т.д.
    • 0
      все про это говорят, но нигде нет конкретного описания подобного решения. Как скрестить, откуда что взять, как и где обновлять.
  • +1
    NESTED SETS: Провел небольшой тест по производительности, вставка в пустое дерево по 1000 записей:
    0001-1000 — 3.5275 сек.
    1001-2000 — 6.2751 сек.
    2001-3000 — 8.4156 сек.
    3001-4000 — 9.9535 сек.
    4001-5000 — 14.0197 сек.
    Тест проводился на хостинге (nichost.ru тариф 301), собственная база MySQL, адаптер БД Zend_DB с включенным профилировщиком.
  • 0
    А еще есть — ordpath, хитрая схема нумерации, опитизированная и под поиск и под вставку новых узлов.
  • 0
    Отличная статья!
    (Правда графы зря были освещены в этой статье. ИМХО, они не нужны здесь.)

    — Народ, с каким фреймворком вы используете Doctrine?
    И совсем не в тему, НО очень интересует, кто как крестил Zend Auth, Zend Acl и Doctrine в Zend контролерах.
    • +1
      Я крестил — mikhailstadnik.com/tuning-zf-with-doctrine
      Acl и Auth дальше сделать достаточно просто через написание собственных адаптеров и плагинов. Работет как часы.
      • 0
        Я крестил немного по другому, но результат тот же. В этом проблем нет. Все отлично работает.

        Проблема заключается в грамотном использовании Acl и Auth. Как крестить контроллеры на работу с Acl, может поделитесь решением?
        Не хочется изобретать велосипед.

        • 0
          Ах. вы об этом… Ну я не думаю, что могу предложить какое-либо стандартное решение. Все зависит от специфики приложения. Мой случай скорее будет частным нежели общим, поэтому как готовое решение давать не буду, но в двух словах скажу.

          У нас на уровне БД структура прав доступа, в которой один из типов объектов на права — это экшены контроллеров, соответственно у нас есть Acl плагин который умеет их обрабатывать. Но для общего случая это довольно грубое решение. Мы-то и хотели все контролировать руками (фактически, пока я не пропишу права на экшн его никто не сможет выполнить)…

          P.S. Подумаю еще на досуге над вашей задачей может че-то путнее в голову придет…
    • 0
      Юзаю с symfony, очень доволен.
  • 0
    > SELECT name, strfind( path, '.') AS level
    > FROM mp_tree
    > WHERE path LIKE '1.1%'; /* Выбираем всю ветку 'VEGETABLES' */;

    Мне кажется, что в данном случае будут выбраны в том числе и ветки: 1.10, 1.11.2 и т.п. Т.е. нужно указывать разделитель:

    WHERE path LIKE '1.1.%'; /* Выбираем всю ветку 'VEGETABLES' */;

    И дальше уже вопрос нужна ли сама ветка 1.1; если да, то придется прописывать разделитель во все пути самым последним символом.
  • 0
    Пробую разобраться с древовидной структурой в Propel, при вставке/изменении записи проблем нет, а вот когда пытаюсь сделать root node происходят странности. Кто нибудь работал с sfPropelActAsNestedSetBehaviorPlugin в админке. Хотелось бы понять как норм построить дерево.
  • 0
    Хочу добавить эту информацию в документацию по Doctrine на русском языке, перевод которой я делаю. Если автор не возражает.
  • 0
    А как быть, если одно дерево является частью других разных нескольких деревьев?
    • 0
      Думаю, нужен пример того что именно необходимо реализовать, чтобы ответить.
      • 0
        image
        «узел1» — это дерево, которое является частью дерева «машина1» и «машина2».
        • 0
          Думаю тут нет ничего сверхестественного, если делать Adjacency List. Просто создаем таблицу для каждой из «сущностей»:

          CREATE TABLE cars (
              `id` BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
              `name` VARCHAR(50) NOT NULL
          ) TYPE=InnoDB DEFAULT CHARSET=utf8;
          
          CREATE TABLE nodes (
              `id` BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
              `name` VARCHAR(50) NOT NULL
          ) TYPE=InnoDB DEFAULT CHARSET=utf8;
          
          CREATE TABLE details (
              `id` BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
              `name` VARCHAR(50) NOT NULL
          ) TYPE=InnoDB DEFAULT CHARSET=utf8;
          


          Теперь заполним эти таблицы данными из представленной схемы:

          INSERT INTO cars VALUES
              (1, 'Машина1'),
              (2, 'Машина2');
          
          INSERT INTO nodes VALUES
              (1, 'Узел1'),
              (2, 'Узел2'),
              (3, 'Узел3');
          
          INSERT INTO details VALUES
              (1, 'Деталь1'),
              (2, 'Деталь2');
          


          Теперь нужно просто создать связи между «сущностями», для этого создаются таблицы связей. Сначала свяжем Машины и Узлы:

          CREATE TABLE car_node (
              `id` BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
              `car_id` BIGINT NOT NULL,
              `node_id` BIGINT NOT NULL
          ) TYPE=InnoDB DEFAULT CHARSET=utf8;
          
          INSERT INTO car_node VALUES
              (1, 1, 1),
              (2, 1, 2),
              (1, 2, 1),
              (2, 2, 3);
          


          Не плохо получилось, добавим связь узлов и деталей.

          CREATE TABLE node_detail (
              `id` BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
              `detail_id` BIGINT NOT NULL,
              `node_id` BIGINT NOT NULL
          ) TYPE=InnoDB DEFAULT CHARSET=utf8;
          
          INSERT INTO node_detail VALUES
              (1, 1, 1),
              (2, 2, 1);
          

          Прошу обратить внимание, что тут второе число это id детали, а третье id узла. Можно было сделать привычнее и расположить вторым узел, но так разнообразнее :)

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

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.