Автоматизация обхода дерева
Теперь, когда вы увидели некоторые полезные вещи, которые вы можете сделать с этой таблицей, пришло время узнать, как мы можем автоматизировать создание этой таблицы. Хотя это хорошее упражнение в первый раз и с небольшим деревом, нам действительно нужен скрипт, который выполняет весь этот подсчет и обход дерева.
Давайте напишем скрипт, который преобразует список смежности в измененную таблицу обхода дерева предзаказа.
<?php
function rebuild_tree($parent, $left) {
// the right value of this node is the left value + 1
$right = $left+1;
// get all children of this node
$result = mysql_query('SELECT title FROM tree '.
'WHERE parent="'.$parent.'";');
while ($row = mysql_fetch_array($result)) {
// recursive execution of this function for each
// child of this node
// $right is the current right value, which is
// incremented by the rebuild_tree function
$right = rebuild_tree($row['title'], $right);
}
// we've got the left value, and now that we've processed
// the children of this node we also know the right value
mysql_query('UPDATE tree SET lft='.$left.', rgt='.
$right.' WHERE title="'.$parent.'";');
// return the right value of this node + 1
return $right+1;
}
?> Это рекурсивная функция. Вы должны начать его с rebuild_tree('Food',1); Затем функция извлекает всех дочерних элементов узла «Еда».
Если дочерних элементов нет, он устанавливает его левое и правое значения. Левое значение задается как 1, а правое значение — это левое значение плюс один. Если есть дочерние элементы, эта функция повторяется и возвращается последнее правильное значение. Это значение затем используется как правильное значение узла «Питание».
Рекурсия делает эту функцию довольно сложной для понимания. Тем не менее, эта функция достигает того же результата, который мы сделали вручную в начале этого раздела. Он обходит дерево, добавляя по одному на каждый узел, который видит. После запуска этой функции вы увидите, что левые и правые значения остаются одинаковыми (быстрая проверка: правильное значение корневого узла должно быть в два раза больше числа узлов).
Добавление узла
Как добавить узел в дерево? Есть два подхода: вы можете сохранить родительский столбец в вашей таблице и просто перезапустить rebuild_tree() или вы можете обновить левое и правое значения всех узлов на правой стороне нового узла.
Первый вариант прост. Для обновления используется метод списка смежности, а для поиска — модифицированный алгоритм обхода дерева предзаказов. Если вы хотите добавить новый узел, вы просто добавляете его в таблицу и устанавливаете родительский столбец. Затем вы просто перезапустите rebuild_tree() Это легко, но не очень эффективно с большими деревьями.
Второй способ добавить и удалить узлы — обновить левое и правое значения всех узлов справа от нового узла. Давайте посмотрим на пример. Мы хотим добавить новый тип фруктов, «Клубника», в качестве последнего узла и потомка «Красный». Сначала нам нужно освободить место. Правильное значение «Red» должно быть изменено с 6 на 8, 7-10 «Yellow» — на 9-12 и т. Д. Обновление «Red» означает, что нам придется добавить 2 ко всем левым и правильные значения больше 5.
Мы будем использовать запрос:
UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
Теперь мы можем добавить новый узел «Клубника», чтобы заполнить новое пространство. Этот узел покинул 6 и справа 7.
INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';
Если мы запустим нашу функцию display_tree()
Food
Fruit
Red
Cherry
Strawberry
Yellow
Banana
Meat
Beef
Pork
Недостатки
Поначалу модифицированный алгоритм обхода дерева предзаказов кажется трудным для понимания. Это, конечно, не так просто, как метод списка смежности. Однако, как только вы привыкнете к левому и правому свойствам, становится ясно, что вы можете сделать почти все с помощью этой техники, что вы могли бы сделать с помощью метода списка смежности, и что модифицированный алгоритм обхода дерева предзаказов намного быстрее. Обновление дерева требует больше запросов, что медленнее, но получение узлов достигается только одним запросом.
Вывод
Теперь вы знакомы с обоими способами хранения деревьев в базе данных. Хотя у меня есть небольшое предпочтение для модифицированного обхода дерева предзаказа, в вашей конкретной ситуации метод списка смежности может быть лучше. Я оставлю это на ваше усмотрение.
И последнее замечание: как я уже сказал, я не рекомендую использовать заголовок узла для ссылки на этот узел. Вы действительно должны следовать основным правилам нормализации базы данных. Я не использовал числовые идентификаторы, потому что это сделало бы примеры менее читабельными.
Дальнейшее чтение
Подробнее о деревьях в SQL от мастера баз данных Джо Селко:
http://searchdatabase.techtarget.com/tip/1,289483,sid13_gci537290,00.html
Два других способа обработки иерархических данных:
http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html
Xindice, «родная база данных XML»:
http://xml.apache.org/xindice/
Объяснение рекурсии:
http://www.strath.ac.uk/IT/Docs/Ccourse/subsection3_9_5.html
Если вам понравилось читать этот пост, вы полюбите Learnable ; место, чтобы узнать новые навыки и приемы у мастеров. Участники получают мгновенный доступ ко всем электронным книгам и интерактивным онлайн-курсам SitePoint, таким как PHP и MySQL для веб-разработчиков для начинающих .