leadaxe
Новичок
На форуме с: May 2007
Cообщений: 25
Город:
 |
Ага вот нашел.
Спасибо что выделил мысль.
| |
| Автор оригинала: ONK
dark-demon, если кратко, то для выборки и построения такого дерева обычно используется рекурсивное составление sql запросов и их выполнение непосредственно в процессе построения дерева. На выборку каждого уровня, каждой отдельной ветки требуется новый SQL запрос.
Для построения среднестатистического дерева в 200 элементов может понадобиться 50 - 70 sql запросов. Много это или нормально для выполнения одного действия каждый решает сам. |
|
Проблема действительно такая есть и она не нова. Но как ее решить тем более на пхп , где движек не быстр не совсем очевидно. Но мы можем выделить рекомендации
Движок ПХП медленный, движок же Базы данных быстрый, это значит что чаще лучше отдать большинство задач на движок 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:
| |
| Автор оригинала: BeGe
ONK проще выбрать всё дерево одним запросом и потом рекурсино обойти массив данных чем. |
|
не проще - затраты ПХП на решение этой задачи очень велики
-~{}~ 10.05.07 12:54:
| |
| Автор оригинала: riff
Наверно я тему не правильно назвал.
Надо было как-то ударение поставить на формирование дерева, а не на то как, сколько и чего вытягиваем из БД. |
|
согласись, забавно ты сделал, задал вопрос на одну тему, а поехало само в другую. Вот так всегда сделаешь пост и не имеешь над ним больше власти.
__________________
Живи в удовольствие! liveafun!
Отредактировано leadaxe 10.05.07 в 09:54
|
Начало | Настройки | Расширенный поиск | Регистрация
18.04.07 11:44