Думаю с проблемой хранения деревьев в MySQL сталкивались многие и мне не нужно объяснять сколько при этом возникает проблем. В данной статье я хочу рассказать об одном из методов хранения деревьев под названием "Вложенные множества" (Nested Sets). Для начала описание метода. Взгляните на рисунок ниже (рисую я плохо ):
На нем представлено дерево, описанное по всем правилам метода "Вложенных множеств".
Квадратами обозначены узлы дерева, красные цифры в центре узлов - просто уникальные идентификаторы узла, а цифры в углах - это левое и правое смещения. Именно в этих двух цифрах - левом и правом смещении заложена вся информация о дереве. И если информацию о смещениях занести в базу данных, то работа с деревом намного упрощается.
Обратите внимание на то, в каком порядке проставлены эти смещения. Если мысленно пройтись по порядку от 1 до 22, то вы обойдете все узлы дерева слева направо. Фактически это путь обхода всех узлов дерева слева направо. Опишу правила по которым эти смещения расставляются:
* Начинать обход дерева нужно с корневого узла и в нем же заканчивать.
* При самом первом входе в узел нужно "оставить" цифру в его левом углу и при последнем выходе из узла нужно оставить цифру в правом углу.
* Все цифры расставляются, начиная с 1.
* Последняя цифра должна быть в 2 раза больше количества узлов дерева (потому что в каждом узле оставляем по 2 по указанным выше правилам)
Данная статья предназначена прежде всего для PHP-программистов. Поэтому я не буду вдаваться в подробности как "вручную" организовать такое дерево в mysql-таблице, поскольку для этого есть готовый класс - CDBTree. Скачать его можно с http://dev.e-taller.net/dbtree/
На этом теорию заканчивается и начинается практика. Предположим нужно сделать каталог ресурсов с категориями неограниченой вложенности. При этом перед программистом возникает несколько микро-задач:
* Нужно сделать вывод дерева категорий
* Нужно получить список ВСЕХ подкатегорий для указанной категории
* Нужно получить список подкатегорий, уровень вложенности которых на единицу больше уровня вложенности указанной категории
* Нужно получить список всех родительских категорий для указанной категории (для посторения пути к текущей категории)
Замечу, что класс CDBTree еще хранит в таблице уровень вложенности для данного узла. Это факт облегчит нам решение задачи номер 3 Для начала создайте таблицу:
CREATE TABLE categories (
cid int(10) unsigned NOT NULL auto_increment,
title varchar(128) NOT NULL default '',
cleft int(10) unsigned NOT NULL default '0',
cright int(10) unsigned NOT NULL default '0',
clevel int(10) unsigned NOT NULL default '0',
PRIMARY KEY (cid),
KEY cleft (cleft, cright, clevel)
) TYPE=MyISAM;
Данная таблица представлена только для примеров. В конце статьи я приведу слова автора класса по поводу организации таблиц для хранения деревьев. А теперь выполните следующий скрипт:
<?
/*
Работа с деревом по алгоритму Nested Sets.
Подготовка таблицы к работе.
Используется класс dbtree.php
Взять его можно: http://dev.e-taller.net/dbtree/
---------------------
Author: Maxim Matykhin.
mailto:
[email protected]
*/
$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(" ",6*$row['clevel']).$row['title']."<br>";
}
?>
В данном случае для расчета величины отступа используется значение clevel. Теперь посмотрим, как получить все подкатегории. Это можно сделать либо с помощью метода enumChildrenAll($cid); либо написав правильный SQL-запрос. Предположим есть категория параметры которой $cleft, $cright и $clevel. Тогда запрос, получающий все дочерние узлы, выглядит так:
SELECT
cid,
title,
clevel
FROM
categories
WHERE
cleft BETWEEN $cleft AND $cright
ORDER BY cleft
Выполнив этот запрос, вы получите все подкатегории для указанной категории Метод enumChildrenAll($cid); также возвращает подкатегории, но он возвращает только их идентификаторы, и нет встроенных методов для того чтобы он возвращал дополнительные поля (конечно же вы можете внести изменения в класс).
Для получения списка подкатегорий, уровень вложенности которых на единицу больше уровня вложенности указанной категории происходит.
SELECT
cid,
title,
clevel
FROM
categories
WHERE
cleft BETWEEN $cleft AND $cright AND
clevel = $clevel+1
ORDER BY cleft
И последнее - определение родительских категорий.
Запрос должен выглядеть так:
SELECT
cid,
title,
clevel
FROM
categories
WHERE
cleft < $cleft AND
cright > $cright
ORDER BY cleft
В классе CDBTree для этого есть метод enumPath($cid).
Теперь об рекомендациях автора класса:
опыт показывает, что структуру с обходом дерева лучше хранить отдельно от
данных, т.к. в этом случае при обновлении таблицы очень долго обновляются
индексы, да и данные могут сделать невозможным формат записи фиксированной
длины, что тоже кардинально скажется на скорости.
Самой оптимальной структурой по-моему будет:
CREATE TABLE categories (
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,
PRIMARY KEY(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 - массив с именами полей таблицы
function getElementInfo($ID)
Возвращает массив с информацией о об элементе с указанным $ID (параметры left, right, level).
function clear($data=array())
данная функция очищает таблицу и вставляет в нее корневой узел дерева.
В массиве $data должна быть информация в виде array("db_field"=>"value", ...)
Поля left, right и level будут вставлены автоматически.
function update($ID, $data)
этот метод используется для изменения информации об указанном элементе. Параметры:
* $ID - идентификатор узла
* $data - массив с обновленными данными. (параметры left, right и level вставлять не нужно)
function insert($ID, $data)
Метод для вставки узла в дерево. Параметры:
* $ID - идентификатор родительского узла
* $data - массив с обновленными данными. (параметры left, right и level вставлять не нужно)
function delete($ID)
Удаляет указанный узел не удаляя его "потомков";
function deleteAll($ID)
Удаляет указанный узел вместе с его "потомков";
function enumChildrenAll($ID)
Определяет всех "потомков" для указанного узла
function enumChildren($ID, $start_level=1, $end_level=1)
Определяет потомков для указанного узла
* $start_level - начальный уровень вложенности узла с которого нужно искать "потомков";
* $end_level - конечный уровень вложенности узла до которого нужно искать "потомков";
Если $end_level не указан, (равен 0) то ищутся все узлы "глубже" $start_level
function enumPath($ID, $showRoot=false)
Определяет всех родителей для указанного узла.
* $showRoot - true, если нужно выводить корневой элемент.
Последние три описанные функции формируют SQL-запрос таким образом, что выводятся только идентификаторы узла.
Остальные методы мне использовать не приходилось. Поэтому описывать их не буду. В последней версии класса появился метод MoveAll для перемещения узлов в дереве, но пока он работает с багами.