Профессиональная разработка Web-приложений.  
Боишься нашего дизайна?
Новости
PDF журнал
Участники проектa
Сотрудничество
Ссылки
Карта сайта
Комментарии
Комментарии к статье
Добавить комментарий
Обсудить на форуме
Информация об авторе
Оценка статьи

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

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


Думаю с проблемой хранения деревьев в 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: 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. Тогда запрос, получающий все дочерние узлы, выглядит так:
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 для перемещения узлов в дереве, но пока он работает с багами.

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


For comment register here
   2003-11-21 11:39
Битая ссылка последняя. Жалко. Хотел как раз почитать.

   2003-11-24 10:17
Ссылка исправлена :)

   2003-12-01 11:28
Э-э, а почему как вам такая схема:

cid
cparent
clevel
cpath

, где clevel - уровень в дереве, cparent - cid родителя, а cpath формируется как-то так:

cid name clevel cparent cpath
001 Элемент 1 1 0 001000000
002 Элемент 2 2 1 001002000
003 Элемент 3 2 1 001003000
004 Элемент 4 3 2 001002004
005 Элемент 5 3 3 001003005

Единственный недостаток - достаточно длинное поле cpath для "высоких" деревьев...

   2003-12-09 13:30
Согласен с sysolitin'ом - таким вариантом лучше хранить дерево. Сам делал. Причем дерево уже сформированное должна база предоставлять (а не скрипт на php формировать !!!!!!) - проверено работает гораздо-гораздо быстрее. А поле cPath - на клиент надо не передавать. Оно используется базой- ее формируется и ее обрабатывается. А насчет высоких деревьев можно не беспокоиться - усе работает и шустренько

   2003-12-10 18:34
Дополнение к статье:
вроде нашлась ошибка в методе moveAll() который перемещает узлы.
Пока что исправленная версия лежит на http://max.phpclub.net/sources/dbtree.phps . Позже будет на dev.e-taller.net/dbtree/
Если опять будет глючить - напишите мне.

2 ???????
> проверено работает гораздо-гораздо быстрее
Что именно ты проверял ? Может тесты покажешь ?

   2003-12-11 14:32
Как бы хорошо было бы увидеть функции перемещения веток и поднятия уровня. В статьях этого нигде нет :)

   2003-12-13 00:25
2 Кроха
Перемещение ветки делается методом $tree->moveAll($id, $new_parent);
$id - идентификатор узла, который нужно переместить (переместиться и все его дочерние узлы)
$new_parent - новый родительский узел для $id
На момент написания статьи этот метод не работал. Сейчас вроде исправлен, я его не особо тестировал. Исправленная версия лежит на :
http://max.phpclub.net/sources/dbtree.phps

Я не понял, что значит "поднятие уровня". Возможно сообщения на форуме в этом треде:
http://phpclub.ru/talk/showthread.php?s=&;threadid=30774&perpage=20&pagenumber=2

   2003-12-16 10:21
Есть ещё один класс для работы с деревьями. http://www.anter.com.ua/myXTree/. Кроме всего прочего он позволяет использовать XPath выражения вместо SQL запросов при выборке данных из дерева, и выдаёт их в виде DOM дерева. Для добавления данных в дерево сначало создаётся дерево DOM (с помощью DOM API или из XML файла), а потом передаётся классу myXTree для сохранения в SQL дереве.

   2003-12-29 16:33
2 mahoune
http://phpclub.ru/talk/showthread.php?s=&;threadid=30774&perpage=20&pagenumber=2

   2004-01-05 20:56
2 sysoletin
А можно попродробнее про формирование поля cpath, поскольку кроме oracle формировать его, помойму, никто не умеет.

   2004-01-06 15:09
2 vova (@) spylog.ru
пример с insert-ами я привел лишь для того чтобы читаетли могли выполнить его и затем эксперимнтировать деревом. Реально задача с множеством вызовов метода insert() встречается редко. Если все же вам надо делать частые вставки - то возможно стоит посмотреть на другие методы хранения деревьев.

   2004-01-08 13:29
Привет, Максим!
С праздником!

По поводу сделанного Вами исправления в функции moveAll:
1. Спасибо.
2. Работает уже лучше.
3. Замечен глюк при перемещении узла уровнем выше (ближе к корню), его потомков раскидало непонятным образом между его новыми братьями.

   2004-01-09 15:03
2 abuse [@] yandex.ru
спасибо, на выходных проверю

   2004-01-19 13:19
Автор загляни сюда:
http://phpclub.ru/talk/showthread.php?postid=292302#post292302

   2004-02-01 14:57
В очередной раз пофиксил баг с moveAll()
В предыдущей версии был баг при перемещении вверх по родительской оси.
Если заметите баги - пишите мне либо здесь в комментариях
Ссылка на исходник прежняя:
http://max.phpclub.net/sources/dbtree.phps

   2004-02-19 20:26
2 karbi[@]killerbus.ru
ты же корень не создал (метод clear())
да и insert надо синхронизировать так, чтобы узлы с указанным parent_id уже существовали

   2004-02-22 17:01
У меня небольшая просьба ко всем интересующимся.
Не надо свои вопросы с форума PHPClub, дублировать здесь в комментриях. Я форум читаю постоянно. Поэтому если в теме будет упоминания про Nested Sets я ваше сообщение на форуме прочту и по возможности отвечу

   2004-03-01 19:13
Кстати, Макс, нашёл баг в методе insert( ).
В переменной $data невозможно в качестве значения передать результат работы функции MySQL.
Например NOW в поле datetime, если таковое было создано в таблице categories. Хотя это скорее не баг, а просто ограничение. ИМХО причина тут $fld_values = '\''.implode('\',\'', array_values($data)).'\',';

   2004-06-02 09:09
Сорри, глупость написал - нужно вместо этого просто вставить (в 162 строке класса) else {$fld_names = '';$fld_values = '';}

   2004-08-19 15:37
Ссылка по теме:
http://pear.php.net/package-info.php?pacid=187 - pear пакет для работы с деревьями DB_NestedSet.

   2004-09-15 02:16
Подскажите где можно скачать ещё обновлённую версию класса. Видно я когда то качал, но руки до него добрались не сразу, и в результате у м меня глюки с moveAll() о которых здесь и говорилось. По указанным ссылкам ничё не грузится. Если можно, скиньте кто нить плз мне на мыло (snook[dog]tut.by) файлики класса. Буду очень благодарен.
p.s. Только мне нужен класс с исправленным багом в moveAll().

   2004-11-26 10:57
Макс, насколько приемлима производительность системы при частых вставках элементов? Насколько надежна система при "одновременной" вставке нескольких элементов разными процессами?

   2004-11-26 17:14
2 Snook
на http://dev.e-taller.net/dbtree/ уже давно лежит версия с исправленным moveAll.
Там один баг остался (см. http://phpclub.ru/talk/showthread.php?s=&;threadid=57241&)

2 Eugene Bond
Женя, ты вроде бы ЖЖ demiurg-а читаешь :)
Он как раз недвано писал сравнение методов хранения деревьев в БД. И сравнительные диаграммы там были. В общем случае я не рекомендую использовать его для такого типа деревьев.
Насчет второго вопроса. Если есть возможность использовать транзакции - то используй. Сбой вполне возможен (на форуме vladax писал)

   2005-05-09 14:32
Максим, использовал ваш класс. Отлично все работает. Один только вопрос-просьба - сделать в классе функцию перемещения элемента по ветке (не в родительский корень, а в своей группе), например MoveUp, MoveDown, а то самому писать функцию как-то не правильно - я так понимаю данный вопрос уже поднимался, т.е. еще кому то нужно тоже самое.

   2005-08-13 11:30
Прошу прощения, что пишу сюда, больше не нашёл куда написать...
А как насчёт не $dbh=new CDataBase("dbname", "localhost", "root", "password"); интерфейса к БД?.. Если это PEAR::DB то ничего не работает.. Или это я неправильный?.. (Т.к. БД может быть не MySQL)

   2007-01-19 17:22
Использую версию от 1.4 09-Nov-2004 ... а баг то в moveAll остался.при переносе с соседней ветки вверх. при пересчете cat_left корневого элемента оказался _меньше_ чем cat_left кажется элемента с соседней ветки. ...

   2007-10-30 17:28
Ещё полезная ссылка по теме: http://www.codenet.ru/db/other/trees/
не очень хороший перевод и ошибки в примерах, но разобраться можно (и нужно!)
тот же подход, но куча примеров и всё разжовано от и до.

(проблемы такого метода возникают, если первичный ключ в таблице составной, а не обычный - ID в одно поле)

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

 
 
 
    © 1997-2008 PHPClubTeam
[]