PHP, SQL, Архитектуры, Базы данныхИерархические структуры данных и Doctrine

Введение

Часть 2 — Иерархические структуры данных и производительность

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

В первую очередь, это связано с тем, что реляционные базы не приспособлены к хранению иерархических структур (как, например, 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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');

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

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

1
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    |
+----+-----------+-----------+

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

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

1
2
3
4
5
6
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 опишем структуру нашей таблицы:

1
2
3
4
5
6
7
8
9
10
11
AlTree:
  tableName: al_tree
  columns:
    id:
      type: integer(8)
      primary: true
      autoincrement: true
    name:
      type: string(50)
      notnull: true
    parent_id: integer(8)

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

1
2
3
4
5
6
7
8
9
10
11
  relations:
    Parent:
      class: AlTree
      local: parent_id
      foreign: id
      type: one
    Children:
      class: AlTree
      local: id
      foreign: parent_id
      type: many

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

1
./doctrine generate-models-yaml

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

1
2
3
4
5
6
7
8
9
10
...
  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-странице, используя рекурсию.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Извлекаем корневой элемент дерева
 */
$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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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. В нем будет храниться информация об уровне вложенности каждой ветки дерева. В принципе, это делать вовсе не обязательно — уровень вложенности может быть достаточно просто вычислен, но так как данный алгоритм оптимизирован как раз для чтения, то почему бы не выиграть в производительности за счет кеширования информации об уровне? Риторический вопрос...

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

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

1
2
3
4
5
6
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 |
+----+-----------+-------+

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

1
2
3
4
5
6
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) из нашего примера, это сделать достаточно просто:

1
2
3
4
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.

1
2
3
4
5
6
7
8
9
10
11
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 использовать блокировки на запись:

1
2
3
LOCK TABLE ns_tree WRITE;
...
UNLOCK TABLES;

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 модели. Например, вы можете хранить в одной таблице несколько деревьев. Для этого, вам необходимо ввести в таблицу дополнительное поле, в котором вы будете хранить идентификатор корня дерева для каждой записи.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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

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

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

1
2
3
4
5
6
7
8
...
    public function setTableDefinition()
    {
        ...
        $this->actAs('NestedSet');
       ...
    }
...

или:

1
2
3
4
5
6
7
8
...
    public function setTableDefinition()
    {
        ...
        $this->actAs('Doctrine_Template_NestedSet');
       ...
    }
...

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

1
2
3
4
5
6
7
8
9
10
...
    public function setTableDefinition()
    {
        ...
        $options = array('hasManyRoots'     => true,
                         'rootColumnName'   => 'root_id');
        $this->actAs('NestedSet', $options);
       ...
    }
...

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

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

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

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

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

За дополнительными примерами и информацией вы можете обратиться к официальной документации 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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, он более поддается изменениям. В то же время остается достаточно удобным для выборки деревьев целиком и их частей. Но, и он не идеален. Особенно по части поиска предков ветки.

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

1
2
3
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 не имеет подходящей функции, но мы можем ее реализовать достаточно просто своими силами:

1
2
3
4
5
6
7
8
9
10
11
12
13
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

Выбор ветки:

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

Результат:

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

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

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

1
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, и как их использовать.

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

Часть 2 — Иерархические структуры данных и производительность

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

Хорошая статьяПлохая статья +16
   |    Опубликовано: Декабрь, 10 2008г.    |    Автор: Михаил Стадник

Комментарии (17) к статье “Иерархические структуры данных и Doctrine”

Оставить комментарий