Построение дерева иерархии с помощью PHP / MySQL
Рассмотрим пример построения дерева иерархии (в развернутом виде) на основе информации из базы данных с помощью PHP и MySQL. Ключ к решению данной задачи — использование рекурсивной функции. Иерархия разделов будет храниться в таблице базы данных MySQL.
Ниже на скриншоте показана данная таблица (catalogue):
Далее напишем следующий PHP-скрипт:
1. Файл dbopen.php (открывает соединение с MySQL)
if (!mysql_select_db($databaseName, $link)) < printf("Ошибка базы данных !"); exit(); >?> 2. Файл index.php (основной скрипт)
Всю работу выполняет рекурсивная функция ShowTree(). Ниже на скриншоте показан пример работы index.php:
Подборка курсов по PHP
4.4 Skillbox еще 3 курса
4.4 GeekBrains еще 1 курс
4.2 Оtus
4.4 HTML Academy
4.5 Hexlet
4.7 HEDU (irs.academy)
Комментарии
P.s я писал на js. не сильно отличается. Спасибо за идею!
var str=»;
function ShowTree(ParentID) var result=SCatList.GetChild(ParentID, false);
Я просто в бешенстве от простоты автора!
Зачем ему $link если он нигде не используется!
И при всем уважении такого результата при этом коде получиться не может, там в исходнике html не пойми что будет!!
Лучше использовать references . Можно все сделать 1 запросом и без рекурсии
вот пример — http://phpblog.com.ua/2010/06/tree-with-references/
Есть ещё один способ, но требующий умного подхода. Выбрать всё из базы одним запросом и запихать в многоуровневый массив, и уже потом работать с массивом. Загвоздка состоит в том, что бы отсортировать массив так, что бы сабы были именно под своими парентами.
К примеру есть такой массив:
Array (
[0] => Array (
[s_id] => 5
[s_title] => Контент сайта
[c_id] => 34
[c_parent] => 0
[c_title] => Контент сайта
)
[1] => Array (
[s_id] => 6
[s_title] => Статьи
[c_id] => 35
[c_parent] => 0
[c_title] => Web дизайн
)
[2] => Array (
[s_id] => 6
[s_title] => Статьи
[c_id] => 36
[c_parent] => 40
[c_title] => Web программирование
)
[3] => Array (
[s_id] => 6
[s_title] => Статьи
[c_id] => 37
[c_parent] => 36
[c_title] => PHP
)
[4] => Array (
[s_id] => 6
[s_title] => Статьи
[c_id] => 38
[c_parent] => 0
[c_title] => JavaScript
)
[5] => Array (
[s_id] => 6
[s_title] => Статьи
[c_id] => 39
[c_parent] => 0
[c_title] => MySQL
)
[6] => Array (
[s_id] => 6
[s_title] => Статьи
[c_id] => 40
[c_parent] => 0
[c_title] => Joomla
)
)
Описание:
[s_id] — ид секции
[s_title] => заголовок секции
[c_id] => ид категории
[c_parent] => родитель категории
[c_title] => заголовок категории
Это полная выборка из бд. Сделать что бы было так
Контент сайта
—Контент сайта
Статьи
—Web дизайн
—JavaScript
—MySQL
—Joomla
—-Web программирование
——PHP
пока никто не смог, а было бы хорошо
@bibendi:
Этот метод стоит использовать, если у вас максимальный размер вложенности состовляет не более 3-4 уровней.
Если же больше, то тут тоже надо смотреть, а как сильно будет нагружатся БД??
Т.е. на сколько часто будет извлекатсья информация, допусти для популярного интернет-магазина с подкатегориями более чем в 2-3 уровня это будет непозволительная роскошь использовать столько ресурсов.
Короче, к чему я всё клоню, есть такой алгоритм Nested Sets (вложенные множества).
Вот его и нужно использовать, если предпологается большая многоуровневая вложенность и/или большая нагрузка на сервер — читай много посетителей.
Конечно, кто-то скажет, что эта бодяга решается с помошью кэширования, безусловно его можно использовать и даже нужно, но в совокупности с этим алгоритмом вы добъётесь впечатляющих результатов скорости, т.к. для извлечения пркатически любой информации из дерева необходимо всего ОДИН запрос в БД.
здесь есть инфа, если кого заинтересовало http://www.getinfo.ru/article610.html
не сочтите за рекламу другого сайта.
Я просто столкнулся с такой проблемой, когда закачик дал задание разработать каталог с 6-8 уровнями вложенности и в каталоге было более 1500 категорий о_О
Уважаемый, для этого и существует кеширование файлов.
Один раз подключились, загнали все у виде массива в файл, а потом просто вытаскиваеш. Когда нужно будет, так и обновиш файл.
Если что, смотри в сторону serialize()
Источник
Вложенные множества в MySQL
Каждому программисту рано или поздно приходится столкнуться с вложенным множеством (известным как дерево или иерархия) в реляционных базах данных. В данной заметке я опишу частный случай работы с таким множеством — модель Nested Sets (далее просто Nested Sets).
Nested Sets (Вложенные множества) подразумевает присвоение каждому узлу в дереве двух дополнительных ключей left key и right key. Для заполнения этих ключей нам придется полностью обойти всё дерево дважды посещая каждый из узлов. В результате выборка из дерева будет происходить довольно быстро. С другой стороны изменение структуры требует пересчета всех ключей в узлах следующих за изменяемым узлом.
Плюсы
В базах, которые не поддерживают рекурсивные запросы (например, MySQL) выборка из дерева происходит быстрее, чем если бы она делалась с помощью хранимой процедуры.
Минусы
Изменения в базе занимают много времени, так как приходится обновлять все левые и правые ключи в записях, идущих после изменяемой.
На схеме представлен простой пример Nested sets:
| Название | Left key | Right key |
|---|---|---|
| Коктейли | 1 | 30 |
| Алкогольные | 2 | 15 |
| С бренди | 3 | 8 |
| Дракон | 4 | 5 |
| Рэднор | 6 | 7 |
| С виски | 9 | 14 |
| Квадро | 10 | 11 |
| Соблазн | 12 | 13 |
| Безалкогольные | 16 | 17 |
| Молочные | 18 | 29 |
| С мороженым | 19 | 22 |
| Комета | 20 | 21 |
| Со сливками | 23 | 28 |
| Чикита | 24 | 25 |
| Килт | 26 | 27 |
Какие выборки можно сделать?
- Все узлы дерева
SELECT * FROM tree ORDER BY left_key - Выбор дочерних узлов
SELECT * FROM tree WHERE left_key >= $left_key AND right_key - Выбор всех родительских узлов
SELECT * FROM tree WHERE left_key = $right_key ORDER BY left_key - Выбор ветки, в которой учавствует узел
SELECT * FROM tree WHERE right_key > $left_key AND left_key < $right_key ORDER BY left_key
Подробнее о работе с деревом Nested sets написано в статье Сергя Томулевича. Очень рекомендую к прочтению.
Конкретные примеры
На работе передо мной встала задача загрузить в MySQL базу классификатор ОКДП который содержит больше 44 тысяч позиций и обязательным условием было использование модели Nested sets. Классификатор распространяется в виде архива, который содержит около 15 файлов в формате XML.
Мною был написан парсер, который загружал категории в MySQL базу и сразу строил ключи. На этом примере отлично видно падение производительности на большом количестве данных в таблице. Первый файл у меня попал в базу меньше, чем за 10 минут, а последний загружался целый час. А классификатор регулярно обновляется 😉
Стало ясно, что гораздо эффективнее будет просто загрузить классификатор в базу, а уже потом строить левые и правые ключи. Для этого была написана следующая процедура, которая отработала у меня минут за 15:
— Схема таблицы, в которой будет располагаться классификатор — Для удобства я буду хранить уровень вложенности level и код родителя parent_code CREATE TABLE ` classifier ` ( ` id ` int( 10 ) unsigned NOT NULL AUTO_INCREMENT, ` level ` int( 11 ) NOT NULL , ` left_key ` int( 11 ) NOT NULL , ` right_key ` int( 11 ) NOT NULL , ` code ` varchar( 45 ) NOT NULL , ` parent_code ` varchar( 45 ) DEFAULT NULL , ` chang_data_time ` timestamp NULL DEFAULT NULL , ` start_data_active ` timestamp NULL DEFAULT NULL , ` name ` text NOT NULL , PRIMARY KEY ( id ), UNIQUE KEY ` id_UNIQUE ` (` 1 `), UNIQUE KEY ` 1 ` ( code ), KEY right_key ( right_key ), KEY left_key ( left_key ) ) ENGINE=InnoDB AUTO_INCREMENT= 1 DEFAULT CHARSET=utf8 COMMENT= ‘Классификатор ОКДП’ ; delimiter $$ DROP PROCEDURE IF EXISTS rebuild_nested_set_tree$$ CREATE PROCEDURE rebuild_nested_set_tree() BEGIN — Изначально сбрасываем все границы UPDATE classifier SET level = 0 , left_key = 0 , right_key = 0 ; — Устанавливаем границы корневым элементам SET @i := 0 ; UPDATE classifier SET left_key = (@i := @i + 1 ), right_key = (@i := @i + 1 ) WHERE parent_code IS NULL ; SET @parent_code := NULL ; SET @parent_right := NULL ; forever: LOOP — Находим элемент с минимальной правой границей — самый левый в дереве SET @parent_code := NULL ; SELECT t.` code `, t.` right_key ` FROM ` classifier ` t, ` classifier ` tc WHERE t.` code ` = tc.` parent_code ` AND tc.` left_key ` = 0 AND t.` right_key ` <> 0 ORDER BY t.` right_key `, t.` code ` LIMIT 1 INTO @parent_code, @parent_right; — Выходим из бесконечности, когда у нас уже нет незаполненных элементов IF @parent_code IS NULL THEN LEAVE forever; END IF ; — Сохраняем левую границу текущего ряда SET @current_left := @parent_right; — Вычисляем максимальную правую границу текущего ряда SELECT @current_left + COUNT (*) * 2 FROM ` classifier ` WHERE ` parent_code ` = @parent_code INTO @parent_right; — Вычисляем длину текущего ряда SET @current_length := @parent_right — @current_left; — Обновляем правые границы всех элементов, которые правее UPDATE ` classifier ` SET ` right_key ` = ` right_key ` + @current_length WHERE ` right_key ` >= @current_left ORDER BY ` right_key `; — Обновляем левые границы всех элементов, которые правее UPDATE ` classifier ` SET ` left_key ` = ` left_key ` + @current_length WHERE ` left_key ` > @current_left ORDER BY left_key; — И только сейчас обновляем границы текущего ряда SET @i := @current_left — 1 ; UPDATE ` classifier ` SET ` left_key ` = (@i := @i + 1 ), ` right_key ` = (@i := @i + 1 ) WHERE ` parent_code ` = @parent_code ORDER BY ` code `; END LOOP ; — Дальше заполняем поля level — Устанавливаем 1-й уровень всем корневым категориям классификатора UPDATE ` classifier ` SET ` level ` = 1 WHERE ` parent_code ` IS NULL ; SET @unprocessed_rows_count = 100500 ; WHILE @unprocessed_rows_count > 0 DO UPDATE ` classifier ` top, ` classifier ` bottom SET bottom.` level ` = top.` level ` + 1 WHERE bottom.` level ` = 0 AND top.` level ` <> 0 AND top.` code ` = bottom.` parent_code `; SELECT COUNT (*) FROM ` classifier ` WHERE ` level ` = 0 LIMIT 1 INTO @unprocessed_rows_count; END WHILE ; END $$ CALL rebuild_nested_set_tree()$$ DROP PROCEDURE IF EXISTS rebuild_nested_set_tree$$
Источник