Хранение древовидных структур в Базах данных

Хранение древовидных структур в Базах данных

Автор:Maxim Matyukhin 

Описание хранения древовидных структур в базах данных по методу вложенных множеств (Nested Sets)

Думаю с проблемой хранения деревьев в MySQL сталкивались многие и мне не нужно объяснять сколько при этом возникает проблем. В данной статье я хочу рассказать об одном из методов хранения деревьев под названием "Вложенные множества" (Nested Sets). Для начала описание метода. Взгляните на рисунок ниже (рисую я плохо):

На нем представлено дерево, описанное по всем правилам метода "Вложенных множеств".
Квадратами обозначены узлы дерева, красные цифры в центре узлов - просто уникальные идентификаторы узла, а цифры в углах - это левое и правое смещения. Именно в этих двух цифрах - левом и правом смещении заложена вся информация о дереве. И если информацию о смещениях занести в базу данных, то работа с деревом намного упрощается.
Обратите внимание на то, в каком порядке проставлены эти смещения. Если мысленно пройтись по порядку от 1 до 22, то вы обойдете все узлы дерева слева направо. Фактически это путь обхода всех узлов дерева слева направо. Опишу правила по которым эти смещения расставляются:

• Начинать обход дерева нужно с корневого узла и в нем же заканчивать.
• При самом первом входе в узел нужно "оставить" цифру в его левом углу и при последнем выходе из узла нужно оставить цифру в правом углу.
• Все цифры расставляются, начиная с 1.
• Последняя цифра должна быть в 2 раза больше количества узлов дерева (потому что в каждом узле оставляем по 2 по указанным выше правилам)

Данная статья предназначена прежде всего для PHP-программистов. Поэтому я не буду вдаваться в подробности как "вручную" организовать такое дерево в mysql-таблице, поскольку для этого есть готовый класс - CDBTree. Скачать его можно с http://dev.e-taller.net/dbtree/

На этом теорию заканчивается и начинается практика. Предположим нужно сделать каталог ресурсов с категориями неограниченой вложенности. При этом перед программистом возникает несколько микро-задач:

• Нужно сделать вывод дерева категорий
• Нужно получить список ВСЕХ подкатегорий для указанной категории
• Нужно получить список подкатегорий, уровень вложенности которых на единицу больше уровня вложенности указанной категории
• Нужно получить список всех родительских категорий для указанной категории (для посторения пути к текущей категории)

Замечу, что класс CDBTree еще хранит в таблице уровень вложенности для данного узла. Это факт облегчит нам решение задачи номер 3 Для начала создайте таблицу:

CREATE TABLE категории (
cid int (10) без знака NOT NULL auto_increment,
title varchar (128) NOT NULL по умолчанию '',
cleft int (10) без знака NOT NULL по умолчанию '0',
cright int (10) unsigned NOT NULL по умолчанию '0',
clevel int (10) без знака NOT NULL по умолчанию '0',
ПЕРВИЧНЫЙ КЛЮЧ (cid),
КЛЮЧ расщелина (расщелина, крит, клевел)
) ТИП = MyISAM;
                  

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

<? /*
   Работа с деревом по алгоритму Nested Sets.
   Подготовка таблицы к работе.
   Используется класс dbtree.php
   Взять его можно: http://dev.e-taller.net/dbtree/

    ---------------------
    Author: Maxim Matykhin.
    mailto: max@webscript.ru
*/$table="categories"; // таблица категорий $id_name="cid";     // имя поля первичного ключа $field_names = array( // имена полей таблицы
   'left' => 'cleft',
   'right'=> 'cright',
   'level'=> 'clevel',
);

require_once "cd.php";
require_once "dbtree.php";$dbh=new CDataBase("dbname", "localhost", "root", "password"); $Tree = new CDBTree($dbh, $table, $id_name, $field_names); // создаем "корневую" запись (см. пояснения к статье) $id=$Tree->clear(array("title"=>"Каталог ресурсов"));$level_2=array(); $level_2[0]=$Tree->insert($id,array("title"=>"Программирование")); $level_2[1]=$Tree->insert($id,array("title"=>"Новости")); $level_2[2]=$Tree->insert($id,array("title"=>"Сопрт")); $level_2[3]=$Tree->insert($id,array("title"=>"Разное"));// теперь создадим несколько записей третьего уровня $level_3=array(); $level_3[0]=$Tree->insert($level_2[0],array("title"=>"PHP")); $level_3[1]=$Tree->insert($level_2[0],array("title"=>"Perl")); $level_3[2]=$Tree->insert($level_2[0],array("title"=>"Delphi"));$level_3[3]=$Tree->insert($level_2[1],array("title"=>"Криминал"));$level_3[4]=$Tree->insert($level_2[2],array("title"=>"Футбол")); $level_3[5]=$Tree->insert($level_2[2],array("title"=>"Шахматы"));$level_3[6]=$Tree->insert($level_2[3],array("title"=>"Медицина")); $level_3[7]=$Tree->insert($level_2[3],array("title"=>"Экология")); $level_3[8]=$Tree->insert($level_2[3],array("title"=>"Промышленность"));
                                               // и для некоторых сделаем четвертый уровень $Tree->insert($level_3[0],array("title"=>"PEAR")); $Tree->insert($level_3[8],array("title"=>"Металлургия")); $Tree->insert($level_3[6],array("title"=>"Морги"));
echo "Таблица заполнена."; ?>

Данный пример просто заполняет таблицу (просто чтобы следующие примеры потестить на ней).
Думаю код здесь ясен. Наверное стоит лишь объяснить строку:

<? $id=$Tree->clear(array("title"=>"Каталог ресурсов")); ?>

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

<?
$query="SELECT * FROM ".$table." ORDER BY cleft ASC"; $result=$dbh->query($query);
while($row = $dbh->fetch_array($result))
{
   echo str_repeat("&nbsp;",6*$row['clevel']).$row['title']."<br>";
} ?>

В данном случае для расчета величины отступа используется значение clevel. Теперь посмотрим, как получить все подкатегории. Это можно сделать либо с помощью метода enumChildrenAll($cid); либо написав правильный SQL-запрос. Предположим есть категория параметры которой $cleft, $cright и $clevel. Тогда запрос, получающий все дочерние узлы, выглядит так:

ВЫБРАТЬ
чид,
заглавие, 
clevel
ОТ
категории
ГДЕ
расщелина между $ расщелиной и $ cright 
ПОРЯДОК РАССЫЛКИ

Выполнив этот запрос, вы получите все подкатегории для указанной категории Метод enumChildrenAll($cid); также возвращает подкатегории, но он возвращает только их идентификаторы, и нет встроенных методов для того чтобы он возвращал дополнительные поля (конечно же вы можете внести изменения в класс).

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

ВЫБРАТЬ
чид,
заглавие, 
clevel
ОТ
категории
ГДЕ
расщелина между $ расщелиной и $ кратом и
Clevel = $ Clevel + 1
ПОРЯДОК РАССЫЛКИ
 

И последнее - определение родительских категорий.
Запрос должен выглядеть так:

ВЫБРАТЬ
чид,
заглавие, 
clevel
ОТ
категории
ГДЕ
расщелина <$ расщелина И
cright> $ cright 
ПОРЯДОК РАССЫЛКИ
                  

В классе CDBTree для этого есть метод enumPath($cid).
Теперь об рекомендациях автора класса:

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

CREATE TABLE категории (
cat_id INT UNSIGNED NOT NULL AUTO_INCREMENT,
cat_left INT UNSIGNED NOT NULL,
cat_right INT UNSIGNED NOT NULL,
cat_level INT UNSIGNED NOT NULL,
ПЕРВИЧНЫЙ КЛЮЧ (cat_id)
KEY (cat_left, cat_right, cat_level)
);

В итоге MySQL за многими запросами даже не будет обращаться к файлу с данными. Ему будет хватать файла с индексами. А когда уже пройдёт всё фильтрование в таблице с деревом, по примари-кею быстро произойдёт линкование с остальными данными. Также добавлю, что автор класса рекомендует использовать его (класс) только для добавления/удаления узлов в дерево, а для получения узлов писать SELECT-запросы самому.

Описание методов класса CDBTree

CDBTree (& $ DB, $ tableName, $ itemId, $ fieldNames = array ())

конструктор
Параметры:

• &$DB - ссылка на объект класса CDatabase (этот класс лежит в архиве с dbtree.php);
• $tableName - имя таблицы, в которой лежит "дерево";
• $itemID - имя первичного ключа таблицы в которой лежит "дерево";
• $fieldNames - массив с именами полей таблицы

функция getElementInfo ($ ID)

Возвращает массив с информацией о об элементе с указанным $ID (параметры left, right, level).

очистка функции ($ data = array ())

данная функция очищает таблицу и вставляет в нее корневой узел дерева.
В массиве $data должна быть информация в виде array("db_field"=>"value", ...)
Поля left, right и level будут вставлены автоматически.

обновление функции ($ ID, $ data)

этот метод используется для изменения информации об указанном элементе. Параметры:

• $ID - идентификатор узла
• $data - массив с обновленными данными. (параметры left, right и level вставлять не нужно)

вставка функции ($ ID, $ data)

Метод для вставки узла в дерево. Параметры:

• $ID - идентификатор родительского узла
• $data - массив с обновленными данными. (параметры left, right и level вставлять не нужно)

функция удаления ($ ID)

Удаляет указанный узел не удаляя его "потомков";

функция deleteAll ($ ID)

Удаляет указанный узел вместе с его "потомков";

функция enumChildrenAll ($ ID)

Определяет всех "потомков" для указанного узла

функция enumChildren ($ ID, $ start_level = 1, $ end_level = 1)

Определяет потомков для указанного узла

• $start_level - начальный уровень вложенности узла с которого нужно искать "потомков";
• $end_level - конечный уровень вложенности узла до которого нужно искать "потомков";
  Если $end_level не указан, (равен 0) то ищутся все узлы "глубже" $start_level

Функция enumPath ($ ID, $ showRoot = false)

Определяет всех родителей для указанного узла.

• $showRoot - true, если нужно выводить корневой элемент.

Последние три описанные функции формируют SQL-запрос таким образом, что выводятся только идентификаторы узла.

Остальные методы мне использовать не приходилось. Поэтому описывать их не буду. В последней версии класса появился метод MoveAll для перемещения узлов в дереве, но пока он работает с багами.

Ссылки по теме:

• http://dev.e-taller.net/dbtree - здесь лежит сам DBTree и некоторые статьи по хранению деревьев в БД