Обход дерева в mysql

Содержание

Вывод дерева mysql
2 ответа 2
Задача отображения деревьев в MySql. Способ отображения на хранимых процедурах
Задача
Вариант решения

Вывод дерева mysql

Где index — это порядок элемента. Нужно одним запросом сформировать путь, получающийся при обходе в глубину. То есть если у нас такой вид:

1 0 1 2 0 2 3 1 1 4 1 2 5 2 1 6 0 3

То выведется 1 3 4 2 5 6 Нужно на чистом mysql без использования php и тд. Заранее спасибо P.S. Менять в структуре, к сожалению, ничего нельзя Заранее спасибо

В PostgreSQL поддерживаются рекурсивные запросы WITH RECURSIVE, а в Oracle иерархические запросы (hierarchical query clause (also known as “CONNECT BY query”) or recursive subquery factoring).

MySQL не поддерживает рекурсивных запросов. А потому вариантов два. Первый — создание хранимой процедуры, которая отдаст требуемые данные. Второй — создание дополнительной таблицы, в которой будут храниться преобразованные из исходного вида данные в удобном для решения поставленной задачи формате плюс код (триггер и/или эвент), актуализирующий эту таблицу при внесении изменений в исходную.

2 ответа 2

В MySQL нет штатных средств для работы с рекурсивными запросами. Но как известно, если очень хочется, то можно (хотя выглядит это жутковато и оптимизации по скорости это не поддается):

select id,path from ( select @path:=if(@id!=id,`index`, coalesce( (select concat(`index`,'/',@path) from Tree1 where ,@path) ) path, @pid:=if(@id!=id,parent, (select parent from Tree1 N where ), @id:=id id, N from Tree1 T, (select @n:=@n+1 N from Tree1,(select @n:=0) N limit 3) Seq, (select @id:=0,@path:='') X order by id, N ) X where N=3 order by path

Так как ни рекурсии ни циклов в обычном смысле слов нет, то запрос эмулирует рекурсию с помощью эмуляции цикла. В качестве цикла используется склейка с любой таблицей, в которой записей не менее, чем максимально возможный уровень иерархии в дереве. В данном примере используется выборка из той же самой таблицы, явно ограниченная limit 3 (если вложенность дерева больше — число надо соответственно увеличить). Собственно данные из этой таблицы не берутся, а создаются порядковые номера ( N ).

Читайте также: Потолок под дерево балки

После этой склейки у нас в выборке появляется по 3 записи с одним и тем же id. На каждой из них, с помощью переменных, мы получаем id очередной родительской ветки, углубляясь по дереву (так как переменные помнят значения, сформированные в предыдущей строке). Самое главное, что мы тут формируем это путь к данной записи в виде индексов сортировки (если index может быть более 9 то для правильной сортировки надо выравнивать его в пути до одинаковой длины с помощью lpad() )

В какой то момент записи родителей заканчиваются, мы дошли до корня дерева, тогда подзапрос индекса родителя возвращает NULL и при этом с помощью coalesce мы сохраняем ранее сформированный путь. Таким образом в последней записи нашего «цикла» у нас гарантированно будет полный путь до данного листа дерева. Нам остается только убрать из выборки рабочие строки цикла с частично сформированными путями, т.е. выбрать только последние строки ( where N=3 ) и отсортировать по пути индексов.

Источник

Задача отображения деревьев в MySql. Способ отображения на хранимых процедурах

Очень хотелось поднять вопрос о древовидных структурах в MySql. А конкретно о выборках и хранении данных…
Пользователям Oracle и PostgresSQL живется хорошо, в этих БД есть встроенные средства выборки рекурентных данных (см. Иерархические (рекурсивные) запросы).
Пользователям Mysql приходится работать уже с тем, что есть, то есть работа на стороне клиента.
Поскольку эта тема не однократно поднималась, то я попробую рассказать о конкретной задаче и способе её решения.

Задача

Есть проект на php, в нем двевовидная структура реализованнная в таблице mysql catalog (id int NOT NULL,pid int NOT NULL, . )
pid — это id родителя. То есть данные хранятся в одной таблице, каждая ячейка ссылается на родительскую. Таким образом формируется все дерево.
Естественно в таблице хранится куча связанных данных, описание которых я опущу, так как они на суть задачи не повлияют, а будут только мешаться.

Пример такого хранения данных:

CREATE TABLE catalog (
id INT NOT NULL PRIMARY ,
pid INT NOT NULL ,
someData text NOT NULL )
comment = «табличка с рекурентной стркутурой»;

* This source code was highlighted with Source Code Highlighter .

id	pid	someData
1	0	Каталог
2	1	Книга 1
3	1	Книга 2
4	3	Глава 1
5	3	Глава 2
6	3	Глава 3

Производится выборка данных всего дерева рекурентно на стороне клиента. Общий объем базы 500Мб, и дальше будет только расти. Поскольку ветвей и узлов много, то общее количество запросов к базе на данный момент колеблется от 300 до 1000.

В результате рекурентной выборки формируется массив данных (зачем-то тоже рекурентного вида), который отдается на сьедение шаблонизатору.
Задача, оптимизировать выборку так, чтобы выдергивать необходимые данные одним запросом (ну или двумя-тремя, но не так, чтобы их было так много… )

Вариант решения

Задача в целом тривиальна. Она неоднократно решалась. Вводятся дополнительные данные, которые используются для ограничения выборки из таблицы. Весь вопрос сводится только к тому, что это за дополнительное поле (поля). Так или иначе дополнительные данные ведут к избыточности, а значит к накладным расходам по поддержке корректности данных.

В публикациях наиболее часто встречается решение с дополнительным поле типа varchar, в котором хранятся id-шники текстом, разделенные спецсимволом. По этому полю осуществляется сортировка и ограничение чем-нибудь типа like %. %.

естественное ограничение на вложенность иерархии.
накладные расходы и сложности по поддержке этого поля. (в моем случае если писать скрипт занимающийся поддержкой этого поля, то он будет просто виснуть по таймауту, а значит нужно делать эти действия в cron)
серьезнная нагрузка на сеть, которая и является основой для постановки задачи, нагрузка не куда не делась, просто она в фоне, а сервер все-равно тормозит.
в случае переноса узлов дерева нужно обновлять данные этого поля.

В итоге получаем достаточно тяжелое и сложное решение. Времени на его реализацию как всегда не было.

Чтобы решить все изложенные выше проблемы, необходимо действовать по другому. Во-первых, формирование дополнительных данных лучше делать там, где эти данные находятся, то есть на стороне базы данных. Во-вторых, поддержка дополнительных данных — накладная операция, поэтому лучше обновлять их каждый раз.

Эта концепция реализуется следующим образом: пишется не сложная процедура, которая бы формировала данные для временной таблички tmp__index, производя рекурентный обход дерева.
Вот реальный код процедуры:

DELIMITER $$
DROP PROCEDURE IF EXISTS `getIndexToTmpTable`$$
/**
main_id — идентификатор корня или метка поиска
search_id — идентификатор для начала поиска
zlevel — максимальный уровень вложенности, чтобы не упрыгать слишком глубоко,
— установить -1 — чтобы отключить ограничение по вложенности
sublevel — текущий уровень вложенности, для того чтобы складировать в базу
— установить 1
*/
CREATE PROCEDURE `getIndexToTmpTable` (
in main_id INT ,
in search_id INT ,
in zlevel INT ,
in sublevel INT )
BEGIN
DECLARE done INT DEFAULT 0;
DECLARE catalog_id INT ;
DECLARE catalog_pid INT ;
DECLARE cur1 CURSOR FOR select id,pid from catalog where pid=search_id;
DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;
IF sublevel
IF zlevel
/** число наобум */
SET max_sp_recursion_depth= 15;
ELSE
SET max_sp_recursion_depth= zlevel+1;
END IF ;
END IF ;
OPEN cur1;
IF main_id = search_id THEN
/** вставим саму запись, чтобы был полный боекомплект */
insert into tmp__index set
pid =( select pid from catalog where limit 1),
rid =main_id,
level = sublevel-1;
END IF ;
/** нужно влючить глубину рекурсии */
REPEAT
FETCH cur1 INTO catalog_id,catalog_pid;
IF NOT done THEN
/** вставим текущую найденную запись */
insert into tmp__index set
pid = catalog_pid,
rid = main_id,
level = sublevel;
/** спустимся по ниже */
call getIndexToTmpTable(main_id,catalog_id,zlevel,sublevel+1);
END IF ;
UNTIL done END REPEAT;
CLOSE cur1;
END $$
DELIMITER ;

Запуск процедуры предваряется созданием временной таблички, а затем простой селект выдирает необходимые данные.

CREATE TEMPORARY TABLE tmp__index(id int ,pid int ,rid int );
call getIndexToTmpTable(,,1,1);
select c.* from catalog as c join tmp__index as t on t.rid=c.id

делаем все 3-я запросами к БД
избавились от проблем связанных с поддержкой дополнительного поля, так как все генерится динамически
данная процедура не может зациклится, mysql ограничивает на глубину рекурсии
мы можем сами контролировать насколько глубоко нужно обойти дерево (то есть до какого уровня)
мы знаем о каждом элементе все, вплоть до того, на каком уровне он находится
вторичное исполнение процедуры на одних и тех же данных можно устранить, используя локальный кеш результата запроса.

переписать все шаблоны на новый лад.
сделать древовидную структуру из линейной.

Так что я сделал так: сформировал каракас дерева на основе ссылок, последовательно помещая ссылку на элемент-дитя в элемент-родитель. После формирования каркаса дерева я проходил по нему рекурентно и создавал уже дерево с реальными данными.

На рисунке показан вид получаемого мной каркаса. Я схематично указал там название поля, но реально там хранятся только идентификаторы в виде $id=>array(. ), где $id — инедтификатор элемента, а массив содержит набор ссылок на корневые элементы массива. Важно понимать, что записи с одним и тем же именем ссылаются на одно и тоже место памяти. Общий объем хранимых в памяти данных — число элементов + накладные расходы нах хранение массива ссылок.

Вот код преобразования, он в внутри класса. Прошу не судить строго, писалось быстро, из-под палки:

protected $_idToData = null ;
protected $_dataArray = null ;
/**
* генерация рекурентно данных на основе дерева ссылок
* для работы заполнить дерево ссылок, массив связки с данными и массив данных
* $_idToData, $_data
*
* @param array& $curItemFrom
* @param array& $curItemTo
*/
protected function _recGenTreeResult(array&$curItemFrom,array&$curItemTo)
foreach ($curItemFrom as $id=>&$list)
if (!isset($ this ->_idToData[$id]) || !isset($ this ->_dataArray[ $ this ->_idToData[$id] ]))
throw new Exception( ‘recursion build error!’ );
$curItemTo[] = $ this ->_dataArray[ $ this ->_idToData[$id] ];
$i = count($curItemTo)-1;
if (count($list))
$curItemTo[$i][ ‘dir’ ] = array();
$ this ->_recGenTreeResult(&$list,&$curItemTo[$i][ ‘dir’ ]);
>
>
>
function listToTree($dataArray)
$ this ->_dataArray = &$dataArray;
$ this ->_idToData = array();
$parentList = array();
$rootIds = array();
// а теперь делаем рекурентную структуру для вывода
// сохраняем id-> num в массиве data для быстрого доступа
foreach ($ this ->_dataArray as $k=>$d)
$ this ->_idToData[$d[ ‘id’ ]] = $k;
foreach ($ this ->_dataArray as $k=>$d)
// делаем соотношения $pid=>array($id, . ), чтобы потом превратить его в дерево
$parentList[$d[ ‘pid’ ]][$d[ ‘id’ ]]= array();
// если есть, то значит у этого товарища есть родитель .
if (isset($ this ->_idToData[$d[ ‘pid’ ]]))
// берем его родителя и делаем в него ссылку на этого товарища
if (isset($parentList[ $ this ->_dataArray[ $ this ->_idToData[$d[ ‘pid’ ]] ][ ‘pid’ ]]))
if (empty($parentList[ $ this ->_dataArray[ $ this ->_idToData[$d[ ‘pid’ ]] ][ ‘pid’ ]][ $d[ ‘pid’ ] ]))
$parentList[ $ this ->_dataArray[ $ this ->_idToData[$d[ ‘pid’ ]] ][ ‘pid’ ]][ $d[ ‘pid’ ] ] = &$parentList[$d[ ‘pid’ ]];
>
else $rootIds [$d[ ‘pid’ ] ] = true ;
>
$result = array();
foreach (array_keys($rootIds) as $pid)
$ this ->_recGenTreeResult(&$parentList[$pid],&$result);
return $result;
>

В итоге, получили вполне работоспособную штуку. В случае большой базы и глубины рекурсии данному решению тоже может быть плохо. конкретно может быть плохо mySql-серверу. я бы решал эту проблему введением кеширующей таблицы (постоянной), которая бы хранила бы результаты спуска от начала определенного элемента, и копировала бы их во временную таблицу. То есть получался бы классический кеш рекурсии, только на SQL. Это близко к методам динамического программирования. Может быть когда-нибудь дореализую, если локального кеша не хватит на стабильную работу. Хотя я думаю, что хватит…

UPD Статья написана Пуниным Николаем (nicolay.punin@gmail.com), у которого, к сожалению, пока нет инвайта.

Источник