Технические науки

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

Каждая запись данной таблицы с идентификатором в поле title ссылается на своего непосредственного родителя, указанного в поле parent.

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

Данное дерево отобразится в следующую таблицу:

+----------+---------+

| parent | title |

+----------+---------+

| | Food |

| Food | Fruit |

| Fruit | Green |

| Green | Pear |

| Fruit | Red |

| Red | Cherry |

| Fruit | Yellow |

| Yellow | Banana |

| Food | Meat |

| Meat | Pork |

+---------+----------+

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

function traverse_children($parent, $level) {

$result = query('SELECT title FROM tree '. 'WHERE

parent="'.$parent.'";');

while ($row = fetch_array($result))

traverse_children($row['title'], $level+1);
С другой стороны, задачи модификации структуры такого дерева являются тривиальными и быстрыми.

Некоторые базы данных поддерживают такой метод представления деревьев на внутреннем уровне, с помощью различных SQL расширений. К примеру, в СУБД Oracle рекурсивный запрос реализуется следующим образом:

• 
  Очень быстрые операции изменения структуры дерева, не зависящие от размера дерева
  

• 
  Медленные рекурсивные выборки
  

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

+----+----------+--------+----------------+

+----+----------+--------+----------------+

| 1 | Food | 0 | /1/ |

| 2 | Fruit | 1 | /1/2/ |

| 3 | Red | 2 | /1/2/3/ |

| 4 | Cherry | 3 | /1/2/3/4/ |

| 5 | Yellow | 2 | /1/2/5/ |

| 6 | Banana | 5 | /1/2/5/6/ |

| 7 | Meat | 1 | /1/7/ |

| 8 | Beef | 7 | /1/7/8/ |

| 9 | Pork | 7 | /1/7/9/ |

+----+----------+--------+-----------------+

Пример SQL выборки из такого дерева:

SELECT * FROM fruit WHERE path NOT LIKE ‘1/2/%’ ORDER BY path

Результат:

+----+--------+--------+-----------------+

| id | title | parent | path |

+----+--------+--------+-----------------+

| 1 | Food | 0 | /1/ |

| 2 | Fruit | 1 | /1/2/ |

| 7 | Meat | 1 | /1/7/ |

| 8 | Beef | 7 | /1/7/8/ |

| 9 | Pork | 7 | /1/7/9/ |

+----+--------+--------+-----------------+

• 
  Быстрые выборки
  
• 
  Достаточно быстрые операции изменения структуры дерева
  

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

Еще одним способом представления деревьев, предложенным Джо Селко в своей книге «SQL for Smarties», являются вложенные множества. Корень дерева является множеством, содержащим в себе все остальные множества, и отношение родитель – потомок выражается вложением одного множества в другое.

Основное правило вложенности элемента звучит так: узел [clft, crgt] является (косвенным) потомком узла [plft, prgt], если выполняется условие:

plft < clft && prgt > crgt

Ориентированный на работу с множествами, данный метод является одним самых естественных по отношению к SQL.

+--------+-------- +-----+-----+

| parent | title | lft | rgt |

+--------+---------+-----+-----+

| | | 1 | 18 |

| Food | Fruit | 2 | 11 |

| Fruit | Red | 3 | 6 |

| Red | Cherry | 4 | 5 |

| Fruit | Yellow | 7 | 10 |

| Yellow | Banana | 8 | 9 |

| Food | Meat | 12 | 17 |

| Meat | Beef | 13 | 14 |

| Meat | Pork | 15 | 16 |

+--------+--------+-----+------+

Приведем пример типичной выборки:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

Результат:

+--------+------- +-----+-----+

| parent | title | lft | rgt |

+--------+--------+-----+-----+

| Food | Fruit | 2 | 11 |

| Fruit | Red | 3 | 6 |

| Red | Cherry | 4 | 5 |

| Fruit | Yellow | 7 | 10 |

| Yellow | Banana | 8 | 9 |

+--------+--------+-----+-----+

Примечательной особенностью данного метода является также его математическая обоснованность. Скажем, количество потомков вычисляется простой формулой:

descendants = ( rgt – lft - 1) / 2

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

Плюсы:

• 
  Быстрые выборки
  
• 
  Естественное представление дерева с помощью SQL
  
• 
  Вычисление количества потомков без лишних обращений к базе данных.
  

• 
  Очень медленные операции изменения структуры дерева, возрастающие по времени с увеличением дерева.