-
Юбилейный DevConfX пройдет 21-22 июня в Москве. Как всегда — Вы решаете, кто попадет в программу секции Backend — голосуйте за интересные доклады
Загрузка данных из БД ввиде дерева.
- Автор темы riff
- Дата начала
riff
Новичок
В двух словах:
select * from `mytable`;
result
array('id'=>'1', 'pid'=>'0', 'name'=>'главная ветка');
array('id'=>'2', 'pid'=>'1', 'name'=>'дочерняя ветка1');
array('id'=>'3', 'pid'=>'1', 'name'=>'дочерняя ветка2');
строим дерево. получаем
соответственно и все под-, под-, ... ветки построятся в свои родительские ветки.
select * from `mytable`;
result
array('id'=>'1', 'pid'=>'0', 'name'=>'главная ветка');
array('id'=>'2', 'pid'=>'1', 'name'=>'дочерняя ветка1');
array('id'=>'3', 'pid'=>'1', 'name'=>'дочерняя ветка2');
строим дерево. получаем
Код:
array('id'=>'1', 'pid'=>'0', 'name'=>'главная ветка', 'nodes'=>
array(
array('id'=>'2', 'pid'=>'1', 'name'=>'дочерняя ветка1'),
array('id'=>'3', 'pid'=>'1', 'name'=>'дочерняя ветка2')
)
);leadaxe
Новичок
Ага вот нашел.
Спасибо что выделил мысль.
Движок ПХП медленный, движок же Базы данных быстрый, это значит что чаще лучше отдать большинство задач на движок MySQL, например.
В примере, что приведен есть существенный недостаток: цикл по всем данным. Это и память и время.
Есть мнение, что задачу можно существенно упростить если ввести избыточность данных в структуру таблицы например:
Итак задача получить ветку от листа до корня быстро:
id, parent_id, data, trace
trace - что поле VarChar(255) содержит список первых (от элемента) родителей элемента (через разделитель, разделитель вначале и в конце).
Например есть дерево:
1
--2
--3
----8
------13
----10
--4
----9
------11
----12
5
--6
--7
и пусть длина поля ограничена 5 символами, тогда:
Для элемента 13 trace должно принять значение: ".8.3."
Для элемента 3 trace должно принять значение: ".1.0."
теперь мы просто читаем строку и имеем список родителей. Понятно что в поле trace поместятся только ближайшие родители, т.е. запрос надо будет повторить от самого дальнего родителя и так пока не дойдем до верху.
Parents=все строки, перечисленные в trace (13)+все строки, перечисленные в trace (3) имеем .8.3..1.0. итак мы получаем всю ветвь
Вывод:
Если длина id ~ 3-4 цифры, то использование поля varchar(255) уменьшает количество запросов в 50-70 раз
Это хорошо работает для неглубоких деревьев и глубоких деревьев.
Теперь, когда мы ознакомились с полем trace и его смыслом, мы можем решать задачу:
дай все дочерние элементы начиная от заданного id
where trace LIKE %.ID.%
Потом, для каждого полученого элемента взять ID и можно повторить запрос, лучше перед этим все слепить в один или идти стандартной рекурсией
Кстати конструкции LIKE %.ID.% и LIKE %.ID.% оr LIKE %.ID2.% имеют почти одинаковую скорость выполнения - т.к. это один пробег по строке.
Как видите прирост в скорости тоже весьма значительный. Если вы не выходите за длину вашего поля и гарантируете это (например, вложенность 50 - это максимум и id (0-100 000) ), то прирост просто великолепный.
Конечно вы в этом случае используете линейный поиск по таблице, а не бинарный (как по рекурсии для каждого эл-та), но сильно сокращаете кол-во запросов. Т.о. для глубоких деревьев (вложенность 10-50) это дает потрясающие результаты, но для деревьев глубиной 0-3 результат на уровне рекурсии. Для деревьев глубиной 3-5 уже имеет смысл использовать этот подход при частом чтении.
Преимущество этого метода перед описанным в том, что вы выносите работу на ядро базы данных.
Недостаток - лишнее поле, усложнение логики. Пробуйте - решайте сами.
-~{}~ 10.05.07 12:51:
-~{}~ 10.05.07 12:54:
Спасибо что выделил мысль.
Проблема действительно такая есть и она не нова. Но как ее решить тем более на пхп , где движек не быстр не совсем очевидно. Но мы можем выделить рекомендации
Движок ПХП медленный, движок же Базы данных быстрый, это значит что чаще лучше отдать большинство задач на движок MySQL, например.
В примере, что приведен есть существенный недостаток: цикл по всем данным. Это и память и время.
Есть мнение, что задачу можно существенно упростить если ввести избыточность данных в структуру таблицы например:
Итак задача получить ветку от листа до корня быстро:
id, parent_id, data, trace
trace - что поле VarChar(255) содержит список первых (от элемента) родителей элемента (через разделитель, разделитель вначале и в конце).
Например есть дерево:
1
--2
--3
----8
------13
----10
--4
----9
------11
----12
5
--6
--7
и пусть длина поля ограничена 5 символами, тогда:
Для элемента 13 trace должно принять значение: ".8.3."
Для элемента 3 trace должно принять значение: ".1.0."
теперь мы просто читаем строку и имеем список родителей. Понятно что в поле trace поместятся только ближайшие родители, т.е. запрос надо будет повторить от самого дальнего родителя и так пока не дойдем до верху.
Parents=все строки, перечисленные в trace (13)+все строки, перечисленные в trace (3) имеем .8.3..1.0. итак мы получаем всю ветвь
Вывод:
Если длина id ~ 3-4 цифры, то использование поля varchar(255) уменьшает количество запросов в 50-70 раз
Это хорошо работает для неглубоких деревьев и глубоких деревьев.
Теперь, когда мы ознакомились с полем trace и его смыслом, мы можем решать задачу:
дай все дочерние элементы начиная от заданного id
where trace LIKE %.ID.%
Потом, для каждого полученого элемента взять ID и можно повторить запрос, лучше перед этим все слепить в один или идти стандартной рекурсией
Кстати конструкции LIKE %.ID.% и LIKE %.ID.% оr LIKE %.ID2.% имеют почти одинаковую скорость выполнения - т.к. это один пробег по строке.
Как видите прирост в скорости тоже весьма значительный. Если вы не выходите за длину вашего поля и гарантируете это (например, вложенность 50 - это максимум и id (0-100 000) ), то прирост просто великолепный.
Конечно вы в этом случае используете линейный поиск по таблице, а не бинарный (как по рекурсии для каждого эл-та), но сильно сокращаете кол-во запросов. Т.о. для глубоких деревьев (вложенность 10-50) это дает потрясающие результаты, но для деревьев глубиной 0-3 результат на уровне рекурсии. Для деревьев глубиной 3-5 уже имеет смысл использовать этот подход при частом чтении.
Преимущество этого метода перед описанным в том, что вы выносите работу на ядро базы данных.
Недостаток - лишнее поле, усложнение логики. Пробуйте - решайте сами.
-~{}~ 10.05.07 12:51:
не проще - затраты ПХП на решение этой задачи очень велики
-~{}~ 10.05.07 12:54:
согласись, забавно ты сделал, задал вопрос на одну тему, а поехало само в другую. Вот так всегда сделаешь пост и не имеешь над ним больше власти.
leadaxe
все, что ты здесь написал, давно и подробно изложено в вики пхпклуба АКА FAQ АКА "Впорос-ответ".
и не следует быть столь категоричным в своих утверждениях.
разные задачи имеют разные решения.
если задача - выбрать из базы 20 записей, то про "затраты очень велики" скажет только параноик.
все, что ты здесь написал, давно и подробно изложено в вики пхпклуба АКА FAQ АКА "Впорос-ответ".
и не следует быть столь категоричным в своих утверждениях.
разные задачи имеют разные решения.
если задача - выбрать из базы 20 записей, то про "затраты очень велики" скажет только параноик.
Предмет разговора малоактуален.
Всего лишь оригинальный способ построить древовидный массив из небольшого дерева, хранящегося в виде Adjacency List.
Основан на получении всего дерева из базы целиком.
Принципиальной раззницы с рекурсивным разбором на стороне пхп не имеет.
Для больших деревьев непригоден.
Всего лишь оригинальный способ построить древовидный массив из небольшого дерева, хранящегося в виде Adjacency List.
Основан на получении всего дерева из базы целиком.
Принципиальной раззницы с рекурсивным разбором на стороне пхп не имеет.
Для больших деревьев непригоден.
пожалуйста.
1. Самый простой, очевидный и удобный способ хранения деревьев и модификации.
2. Получение дерева - тоже не слишком сложная операция.
2. Слова "сложно, рутинно и медленно" не относятся к небольшим, как я отмечал, деревьям.
Смысл: простое дерево, простая обработка, ограничение на размер.
В принципе, все это было ясно и из моего предыдущего поста.
постарайся, чтобы мне не пришлось все это повторять в третий раз.
1. Самый простой, очевидный и удобный способ хранения деревьев и модификации.
2. Получение дерева - тоже не слишком сложная операция.
2. Слова "сложно, рутинно и медленно" не относятся к небольшим, как я отмечал, деревьям.
Смысл: простое дерево, простая обработка, ограничение на размер.
В принципе, все это было ясно и из моего предыдущего поста.
постарайся, чтобы мне не пришлось все это повторять в третий раз.
Ты все никак не избавишься от комплекса идеального метода.
А от него, скажу я тебе, вреда куда больше, чем от таких вот "порочных" методов.
У тебя в голове одни штампы: "на строне пхп рутинно". "база все сделает быстро".
В результате у тебя появился чудовищный способ, основанный на like. Который будет тормозить на больших объёмах, поскольку like не использует индексы.
при котором просто дерево целиком построить невозможно.
Способы надо делить не на "порочные" и "непорочные" а не подходящие для данной конкретной задачи и неподходящие.
А еще надо учиться видеть много критериев для оценки, а не один.
И очень важно различать весовые коэффициенты этих критериев.
А от него, скажу я тебе, вреда куда больше, чем от таких вот "порочных" методов.
У тебя в голове одни штампы: "на строне пхп рутинно". "база все сделает быстро".
В результате у тебя появился чудовищный способ, основанный на like. Который будет тормозить на больших объёмах, поскольку like не использует индексы.
при котором просто дерево целиком построить невозможно.
Способы надо делить не на "порочные" и "непорочные" а не подходящие для данной конкретной задачи и неподходящие.
А еще надо учиться видеть много критериев для оценки, а не один.
И очень важно различать весовые коэффициенты этих критериев.
ss25_satana
Новичок
А кто нить писал процедуру удаления веток для кода предоставленого топикстартером?
ss25_satana
Новичок
Я к примеру удаляю одну из родительских веток дочерние потеряются при выводе.
т.е. при удалении родительской ветки нужно коректное удаление дочерних.
еще не понятно как вывести не все дерево а его часть ((
т.е. при удалении родительской ветки нужно коректное удаление дочерних.
еще не понятно как вывести не все дерево а его часть ((
ss25_satana
Новичок
из БД естественно.
удали к примеру запись в которой pid = 0 дочерние ветки при выводе в браузер "потеряются" а в БД они останутся.
понял.