---------------------------------
При создании сайта возник вопрос хранения древовидных структур в БД. Например, как хранить многоуровневое меню, или комментарии к сообщениям в базе данных?
В связи с этим решил разобраться с вопросом хранения иерархических структур в MySQL (да и вообще, в реляционных БД) применительно к PHP. Перечитал много материалов по этому поводу и вот теперь созрел для написания чего-то наподобие статьи - чтобы до конца разобраться с этим вопросом и привести свои мысли в порядок. К тому же, тема эта актуальна всегда, и в будущем будет куда заглянуть, чтобы освежить память по этому поводу.
Основы.
Как же вообще можно хранить древовидные структуры в реляционных БД?
Для этого существует несколько методов, очень кратко об основных:
1. Метод Смежных вершин (Ajacency List).
Принцип: в каждой строке таблицы хранятся id узла и id его родителя.
Достоинства: простота и высокая скорость вставки новых записей (узлов) и перемещения существующих, неограниченная глубина вложенности.
Недостатки: сложность выборки подчиненных и родительских узлов. Необходимость рекурсивной выборки.
2. Метод Материализованного пути (Materialized Path).
Принцип: в таблице хранится путь к узлу.
Достоинства: простота выборки подчиненных и родительских узлов.
Недостатки: ограниченная глубина вложенности, более сложный процесс создания новых узлов и перемещения существующих.
3. Метод Вложенных множеств (Nested Sets).
Принцип: в таблице хранятся правый и левый ключ каждого узла.
Достоинства - очень быстрая выборка подчиненных и родительских узлов, неограниченная глубина вложенности.
Недостатки: сложность создания новых узлов, большая сложность перемещения веток.
Существуют и другие методы (например, Вложенных интервалов), но я остановлюсь на методе Nested Sets.
Более подробно о преимуществах и недостатках каждого из них можно почитать, например, здесь.
Итак, Nested Sets.
Основной принцип метода - каждый узел описывается с помощью указания id, правого и левого ключа (см. схему ниже). Часто для удобства добавляют еще один параметр - уровень узла.
Как видно на рисунке, пункты (узлы) имеют следующие ключи:
пункт левый ключ правый ключ уровень
п.1 1 12 0
п.1.1 2 3 1
п.1.2 4 11 1
п.1.2.1 5 6 2
п.1.2.2 7 8 2
п.1.2.3 9 10 2
Такой принцип позволяет легко выбрать предков и потомков узла из дерева.
Выборка всего дерева:
SELECT * FROM `таблица` ORDER BY `левый ключ`;
Выборка предков:
SELECT * FROM `таблица` WHERE `левый ключ` < 'левый ключ узла' AND `правый ключ` > 'првый ключ узла' ORDER BY `левый ключ`;
Выборка потомков:
SELECT * FROM `таблица` WHERE `левый ключ` > 'левый ключ узла' AND `правый ключ` < 'првый ключ узла' ORDER BY `левый ключ`;
Но если мы захотим вставить новый узел или перенести существующий, потребуется изменить ключи у многих других узлов.
Например, если мы добавляем узел п.1.1.1, то ключи изменятся у всех узлов (см. схему ниже).
Теперь узлы имеют такие ключи:
пункт левый ключ правый ключ уровень
п.1 1 14 0
п.1.1 2 5 1
п.1.1.1 3 4 2
п.1.2 6 13 1
п.1.2.1 7 8 2
п.1.2.2 9 10 2
п.1.2.3 11 12 2
На этом я закончу разговор об основах, подробнее о методе Вложенных множеств можно почитать здесь.
Были мысли написать свой класс для работы с деревьями, даже набросал интерфейс с необходимыми методами. Но потом решил не изобретать велосипед, а воспользоваться существующими решениями. Таким образом, в результате поисков я познакомился с ORM Doctrine. Материалов на русском по ней не так много, поэтому информацию я брал с официального сайта проекта. Значительная часть приведенного ниже текста написана на основе статьи Hierarchical Data (англ.).
На загрузке и установке ORM Doctrine я останавливаться не буду, информация об этом есть на официальном сайте.
Для простоты примеры кода буду приводить без тегов <?php ?>. В качестве основы буду использовать таблицу для хранения меню футбольного сайта.
Установка соединения.
За установку соединения с БД отвечает статический метод connection ("параметры драйвера PDO", "имя соединения") класса Doctrine_Manager;
$conn = Doctrine_Manager::connection('mysql://username:password@localhost/test', 'connection 1');username - имя пользователя
password - пароль
localhost - хост
test - имя базы данных
connection 1 - имя соединения
Создание модели по принципу Nested Sets
Для этого создадим таблицу `menu`:
CREATE TABLE `menu` (`id` INT PRIMARY KEY AUTO_INCREMENT,
`reference` VARCHAR(255) UNIQUE KEY DEFAULT NULL,
`rusname` VARCHAR(255) DEFAULT NULL,
`lft` INT,
`rgt` INT,
`level` INT);
Чтобы модель вела себя как вложенное множество, создаем класс Menu, который наследуем от класса Doctrine_Record, и перегружаем в нем методы setTableDefinition() и setUp() с указанными параметрами.
//файл menu.lib.php
//define('MYROOT', str_replace('\\', '/', $_SERVER['DOCUMENT_ROOT']));
/**
* Подключаем классы ORM Doctrine
*/
require_once MYROOT . 'doctrine/Doctrine.php';
spl_autoload_register(array('Doctrine', 'autoload'));
class Menu extends Doctrine_Record
{
public function setTableDefinition()
{
$this->setTableName('menu');
$this->hasColumn('reference', 'string', 255);
$this->hasColumn('rusname', 'string', 60);
$this->hasColumn('lft', 'integer');
$this->hasColumn('rgt', 'integer');
$this->hasColumn('level', 'integer');
}
public function setUp()
{
$this->actAs('NestedSet');
}
}
id - собственно, id узла - автоинкрементное поле, первичный ключ
reference - ссылка (должна быть уникальной), для себя я записываю в это поле все, что хранится в $_SERVER['QUERY_STRING']
rusname - русское имя пункта меню
lft - левый ключ (создается автоматически)
rgt - правый ключ (создается автоматически)
level - уровень (создается автоматически)
Если в таблице `menu` вы планируете хранить не одно дерево, а несколько, то в таблицу нужно добавить поле root_id (INT)- в нем будет храниться id корневого узла, а метод setUp() нужно переписать так:
//файл menu.lib.php
public function setUp()
{
$options = array(
'hasManyRoots' => true,
'rootColumnName' => 'root_id'
);
$this->actAs('NestedSet', $options);
}
Создание корневого узла.
В новом файле test.php подключаем файл с нашим классом.
Создаем корневой узел (страница "Главная", ссылка - "page=main").
//файл test.php
include 'menu.lib.php';
$node = new Menu();
$node->reference = 'page=main';
$node->rusname = 'Главная';
$treeObject = Doctrine_Core::getTable('Menu')->getTree();
$treeObject->createRoot($node);
Выбираем все дерево (о выборке читайте ниже) и проверяем.
$tree = Doctrine_Core::getTable('Menu')->getTree()->fetchTree();
foreach ($tree as $node)
{
echo str_repeat(' ', $node['level'])
. $node['rusname'] . '<br/>';
}
Результат:
Главная
Создание узла (не корневого).
Узлы можно создавать с помощью следующих методов.
insertAsLastChildOf($parent) - вставить в качестве последнего по порядку дочернего узла в ветку $parent
insertAsFirstChildOf($parent) - вставить в качестве первого по порядку дочернего узла в ветку $parent
insertAsNextSiblingOf($other) - в качестве соседнего узла после узла $other
insertAsPrevSiblingOf($other) - в качестве соседнего узла перед узлом $other
insertAsParentOf($child) - вставить в качестве родителя узла $child
Создаем дочерний элемент (страница "Лига Чемпионов", ссылка - "page=cl") в родительской ветке "Главная" ("page=main").
$node = new Menu();
$node->reference = 'page=cl';
$node->rusname = 'Лига чемпионов';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=main');
$node->getNode()->insertAsLastChildOf($parentnode);
Результат:
Главная
Лига чемпионов
Создаем дочерний элемент (страница "Новости", ссылка - "page=news"), ставим его по порядку первым с помощью метода insertAsFirstChildOfNode() в родительской ветке "Главная" ("page=main").
$node = new Menu();
$node->reference = 'page=news';
$node->rusname = 'Новости';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=main');
$node->getNode()->insertAsFirstChildOf($parentnode);
Результат:
Главная
Новости
Лига чемпионов
Создаем дочерний элемент (страница "Лига Европы", ссылка - "page=el"), ставим его по порядку последним с помощью метода insertAsLastChildOfNode() в родительской ветке "Главная" ("page=main").
$node = new Menu();
$node->reference = 'page=el';
$node->rusname = 'Лига Европы';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=main');
$node->getNode()->insertAsLastChildOf($parentnode);
Результат:
Главная
Новости
Лига чемпионов
Лига Европы
Подобным образом добавляем еще несколько узлов.
Свернутый текст
$node = new Menu();
$node->reference = 'page=el&year=2012';
$node->rusname = '2012';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=el');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=el&year=2011';
$node->rusname = '2011';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=el');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=el&year=2010';
$node->rusname = '2010';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=el');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=cl&year=2012';
$node->rusname = '2012';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=cl');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=cl&year=2011';
$node->rusname = '2011';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=cl');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=cl&year=2010';
$node->rusname = '2010';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=cl');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=el&year=2012§ion=calendar';
$node->rusname = 'Календарь';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=el&year=2012');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=el&year=2012§ion=results';
$node->rusname = 'Результаты';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=el&year=2012');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=el&year=2012§ion=teams';
$node->rusname = 'Команды';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=el&year=2012');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=cl&year=2012§ion=calendar';
$node->rusname = 'Календарь';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=cl&year=2012');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=cl&year=2012§ion=results';
$node->rusname = 'Результаты';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=cl&year=2012');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=cl&year=2012§ion=teams';
$node->rusname = 'Команды';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=cl&year=2012');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=news&article=1';
$node->rusname = 'Новость 1';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=news');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=news&article=2';
$node->rusname = 'Новость 2';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=news');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=news&article=3';
$node->rusname = 'Новость 3';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=news');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
$node = new Menu();
$node->reference = 'page=news&article=4';
$node->rusname = 'Новость 4';
$parentnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=news');
$node->getNode()->insertAsLastChildOf($parentnode);
unset($node);
Результат:
Главная
Новости
Новость 1
Новость 2
Новость 3
Новость 4
Лига чемпионов
2012
Календарь
Результаты
Команды
2011
2010
Лига Европы
2012
Календарь
Результаты
Команды
2011
2010
Удаление узла.
Удаляем элемент (страница "Лига чемпионов -> 2012", ссылка - "page=сl&year=2012"), при этом удаляются и все подчиненные узлы.
$node = Doctrine_Core::getTable('Menu')->findOneByReference('page=cl&year=2012');
$node->getNode()->delete();
Результат:
Главная
Новости
Новость 1
Новость 2
Новость 3
Новость 4
Лига чемпионов
2011
2010
Лига Европы
2012
Календарь
Результаты
Команды
2011
2010
Перемещение узла
Узлы можно перемещать с помощью следующих методов.
moveAsLastChildOf($other) - перемещает в качестве последнего по порядку дочернего узла в ветку $other
moveAsFirstChildOf($other) - перемещает в качестве первого по порядку дочернего узла в ветку $other
moveAsPrevSiblingOf($other) - перемещает в качестве соседнего узла перед узлом $other
moveAsNextSiblingOf($other) - перемещает в качестве соседнего узла после узла $other
Перемещаем узел "2012" (reference - "page=el&year=2012") из ветки "Лига Европы" в ветку "Лига чемпионов" (reference - "page=cl") последним по порядку узлом с помощью метода moveAsLastChildOf($node).
$node = Doctrine_Core::getTable('Menu')->findOneByReference('page=cl');
$childnode = Doctrine_Core::getTable('Menu')->findOneByReference('page=el&year=2012');
$childnode->getNode()->moveAsLastChildOf($node);
Результат:
Главная
Новости
Новость 1
Новость 2
Новость 3
Новость 4
Лига чемпионов
2011
2010
2012
Календарь
Результаты
Команды
Лига Европы
2011
2010
Выборка.
В ORM Doctrine существуют несколько методов для выборки узлов (см. полный список методов ниже).
Выборка всего дерева.
$tree = Doctrine_Core::getTable('Menu')->getTree()->fetchTree();
foreach ($tree as $node)
{
echo str_repeat(' ', $node['level'])
. $node['rusname'] . '<br/>';
}
Результат:
Главная
Новости
Новость 1
Новость 2
Новость 3
Новость 4
Лига чемпионов
2011
2010
2012
Календарь
Результаты
Команды
Лига Европы
2011
2010
Выборка всех предков узла (Новость 2, reference - "page=news2").
$node = Doctrine_Core::getTable('Menu')->findOneByReference('page=news&article=2');
$ancestors = $node->getNode()->getAncestors();
foreach ($ancestors as $ancestor)
echo $ancestor['rusname'] . '<br/>';
Результат:
Главная
Новости
Выборка соседей (Новость 2, reference - "page=news2").
$node = Doctrine_Core::getTable('Menu')->findOneByReference('page=news&article=2');
$siblings = $node->getNode()->getSiblings();
foreach ($siblings as $sibling)
echo $sibling['rusname'] . '<br/>';
Результат:
Новость 1
Новость 3
Новость 4
Выборка потомков (Лига чемпионов, reference - "page=cl").
$node = Doctrine_Core::getTable('Menu')->findOneByReference('page=cl');
$descendants = $node->getNode()->getDescendants();
foreach ($descendants as $descendant)
echo str_repeat(' ', $descendant['level'])
. $descendant['rusname'] . '<br/>';
Результат:
2011
2010
2012
Календарь
Результаты
Команды
Функция создания меню "хлебные крошки"
В качестве примера практического применения метода Nested Set от ORM Doctrine привожу функцию создания меню типа "Хлебные крошки" или Breadcrumbs (по сути, ради этого я и начал мурыжить эту ORM).
//define('MYHOST', 'http://' . $_SERVER['HTTP_HOST']);
/**
* Функция для создания меню типа "Хлебные крошки"
* @param string - ссылка на страницу (QUERY_STRING)
* @return string - html-код меню "Хлебные крошки"
*/
function breadcrumbs ($querystring)
{
$breadcrumbs = '';
$node = Doctrine_Core::getTable('Menu')->findOneByReference($querystring);
//Если узел корневой, то предков не ищем
if (!$node->getNode()->isRoot())
{
$ancestors = $node->getNode()->getAncestors();
}
if (isset($ancestors))
{
foreach ($ancestors as $ancestor)
{
$breadcrumbs .= '<a href="' . MYHOST . 'index.php?'
. $ancestor['reference'] . '">'
. $ancestor['rusname'] . '</a> » ';
}
}
$breadcrumbs .= $node->rusname;
return $breadcrumbs;
}
Вызываем функцию со ссылкой на страницу Новости №3 (reference - "page=news&article=3" в таблице `menu`) в качестве аргумента
echo breadcrumbs('page=news&article=3');
Результат:
Главная » Новости » Новость 3
Этот обзор далеко не полный, поэтому ниже привожу список методов класса Doctrine_Node_NestedSet, с помощью которых можно осуществлять разнообразные операции со вложенным множеством, например, проверять наличие соседей, дочерних элементов, извлекать предков, потомков, вручную определять ключи узлов, проверять их валидность и т.д. Перевод мой, строго прошу не судить - я в веб-программировании (да и в программировании вообще) человек новый. Хотелось бы услышать ваши отзывы. И главное, интересна ли эта тема и стоит ли ее продолжать. Впоследствии данный пост буду редактировать, возможно, добавлю что-то еще.
Полный список методов для работы с узлами класса Doctrine_Node_NestedSet
(описание этого класса здесь(англ.))
Свернутый текст
void addChild(mixed record) - добавляет узел в качестве последнего дочернего элемента записи.
void delete() - удаляет узел и всех его потомков.
void detach() - убирает узел из дерева, устанавливая значения lft и rgt = 0.
mixed getAncestors(mixed depth, integer deth) - выбирает всех предков узла.
mixed getChildren() - выбирает дочерние узлы (только прямых потомков).
mixed getDescendants(mixed depth, mixed includeNode) выбирает узлы - потомки (только прямых потомков).
Doctrine_Record getFirstChild() - выбирает запись первого дочернего узла либо пустую запись.
Doctrine_Record getLastChild() - выбирает запись последнего дочернего узла либо пустую запись.
int getLeftValue() - выбирает левый ключ узла.
int getLevel()gets - выбирает уровень (глубину) узла.
Doctrine_Record getNextSibling() - выбирает запись следующего узла-соседа либо пустую запись.
int getNumberChildren() - выбирает количество дочерних узлов.
int getNumberDescendants() - выбирает количество узлов-потомков (всех потомков, а не только дочерние узлы).
Doctrine_Record getParent() - выбирает запись узла-родителя либо пустую запись.
string getPath(string seperator, mixed includeRecord, bool includeNode) - возвращает путь к узлу от корня, использует метод record::toString() для получения имен узлов.
Doctrine_Record getPrevSibling() - выбирает запись предыдущего узла-соседа либо пустую запись.
int getRightValue() - выбирает правый ключ узла.
void getRootValue() - выбирает id корневого узла.
array getSiblings(mixed includeNode) - выбирает соседей узла.
bool hasChildren() - проверяет, есть ли у узла дочерние узлы.
bool hasNextSibling() - проверяет, есть ли у узла сосед справа.
bool hasParent() - проверяет, есть ли у узла узел-родитель.
bool hasPrevSibling() - проверяет, есть ли у узла сосед слева.
bool insertAsFirstChildOf(mixed dest) - вставляет узел в качестве первого по порядку дочернего узла указанного узла.
bool insertAsLastChildOf(mixed dest) - вставляет узел в качестве последнего по порядку дочернего узла указанного узла.
bool insertAsNextSiblingOf(mixed dest) - вставляет узел в качестве следующего соседа указанного узла.
bool insertAsParentOf(mixed dest) - вставляет узел в качестве родителя указанного узла.
bool insertAsPrevSiblingOf(mixed dest) - вставляет узел в качестве предыдущего соседа указанного узла.
bool isAncestorOf(mixed subj) - проверяет, является ли узел предком указанного узла.
bool isDescendantOf(mixed subj) - проверяет, является ли узел потомком указанного узла.
bool isDescendantOfOrEqualTo(mixed subj) - проверяет, является ли узел потомком либо соседним узлом для указанного узла.
bool isEqualTo(mixed subj) - проверяет, является ли узел соседним узлом для указанного узла.
bool isLeaf() - проверяет, есть ли у узла дочерние узлы.
bool isRoot() - проверяет, является ли узел корневым узлом.
bool isValidNode(mixed record) - проверяет валидность узла.
void makeRoot(mixed newRootId) - делает узел с указанным id корневым узлом.
void moveAsFirstChildOf(mixed dest) - перемещает в качестве первого по порядку дочернего узла записи.
void moveAsLastChildOf(mixed dest) - перемещает в качестве последнего по порядку дочернего узла записи.
void moveAsNextSiblingOf(mixed dest) - перемещает в качестве соседнего узла после узла (вставляет справа).
void moveAsPrevSiblingOf(mixed dest) - перемещает в качестве соседнего узла перед узлом (вставляет слева).
void setLeftValue(mixed lft, int ) - записывает новое значение левого ключа узла.
void setRightValue(mixed rgt, int ) - записывает новое значение правого ключа узла.
void setRootValue(mixed value, int ) - записывает новое значение id для корневого узла.