Иерархические структуры данных

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

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

Основные запросы, при работе с иерархическим списком:

  • получения потомков элемента;
  • получения уровня вложенности элемента;
  • получения полного пути от элемента до корня иерархии;
  • операции вставки, удаления, перемещения элемента и его потомков;
  • получение непосредственных потомков/предков.

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

Структура таблицы при этом выглядит следующим образом:

CREATE TABLE `categories` (
`id` int(10) unsigned NOT NULL default '0',
`name` varchar(100) default NULL,
`parent` int(10) unsigned default NULL,
PRIMARY KEY USING BTREE (`cat_id`)
) ;

Но у этого метода есть существенные недостатки:

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

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

Чтобы свести эти недостатки к минимуму необходимо добавить в структуру информацию о полном пути и уровне.

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

CREATE TABLE `parents` (
`cat_id` int(10) unsigned default NULL,
`par_id` int(10) unsigned default NULL
) ;

Подобная схема легко позволяет получить любую информацию об иерархических элементах одним запросом.

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

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

SELECT count(cat_id) FROM parents WHERE cat_id =7;

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

Записи