Комментарии 30
Всё зависит от того процента информации, которое достанется клиенту. Если ему достаётся 50-100% от содержимого дерева - то это вообще самый лучший способ, если 99% информации не используется (а это значит что дерево велико) - то вы зря гоняете кучу данных между SQL-сервером и PHP-скриптом и зря напрягаете интерпретатор PHP, если где-то посередине - то подумайте куда будут склоняться выши запросы в типичном случае...
У меня ного маленьких деревьев, которые нужны целиком для генерации стрницы.
Если данные нужны целиком - то это самый разумный способ. Сериализация и десериализация в PHP весьма быстры и никакой другой способ не даст тебе выигрыша в скорости/памяти. Есть проигрыш при добавлении данных в таблицу, но в большинстве Web-приложений им можно пренебречь. Единственная (но зачастую весьма серъёзная) беда этого способа - сериализация/десериализация данных, которые вообще можно было бы не трогать, но если этого нет - то ни о каких других вариантах и думать не стоит...
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Очевидный недостаток — для поиска по этим элементам придется сделать какой-то хитрый поиск.
Было бы гораздо правильнее хранить сериализованное дерево в memcache, а всю структуру (каждый элемент — строка в таблице) в базе.
Было бы гораздо правильнее хранить сериализованное дерево в memcache, а всю структуру (каждый элемент — строка в таблице) в базе.
НЛО прилетело и опубликовало эту надпись здесь
О, коллега по несчастью :)
Мне приходилось боротся с этой задачей давно, я решил вопрос через подполнительное поле (`all_parents`), в котором в "[]" записывались значения всех предыдущих `parent_id`
Когда мне нужно было получить только ветку начиная с элемента 10 я, чтобы не выбирать базу рекурсивно (это реально жестоко) и не забирать таблицу целиком (что чуть лучше но тоже хрень) выбирал по типу: select * where `all_parents` LIKE '%[10]%'
Ну а потом уже средствами php разбирал полученный результат в дерево. Т.к. сами деревья были небольшие (20-30 элементов) php их строил моментально, в итоге все летало
Мне приходилось боротся с этой задачей давно, я решил вопрос через подполнительное поле (`all_parents`), в котором в "[]" записывались значения всех предыдущих `parent_id`
Когда мне нужно было получить только ветку начиная с элемента 10 я, чтобы не выбирать базу рекурсивно (это реально жестоко) и не забирать таблицу целиком (что чуть лучше но тоже хрень) выбирал по типу: select * where `all_parents` LIKE '%[10]%'
Ну а потом уже средствами php разбирал полученный результат в дерево. Т.к. сами деревья были небольшие (20-30 элементов) php их строил моментально, в итоге все летало
Я конечно не претендую на идеальность, но в то время это было очень простое и логичное решение. Сделал бы я так же сейчас? Незнаю, может быть ;)
Даже интересно стало, решил вспомнить как работало :) Вроде так:
"-" для наглядности вложенности
Поля: имя - id,parent_id,all_parents
-мячи - 1,0,[0]
--футубол - 2,1,[0][1]
---красный - 4,2,[0][1][2]
----в полоску - 9,4,[0][1][2][4]
---синий - 5,2,[0][1][2]
---зеленый - 6,2,[0][1][2]
--теннис - 3,1,[0][1]
---зеленый - 7,1,[0][1][3]
-груши - 8,0,[0]
Для выбора ветки "футбол"
select * from `table` where `id`=2 OR `all_parents` LIKE '%[2]%'
В ответ получаем всю нужную ветку
--футубол - 2,1,[0][1]
---красный - 4,2,[0][1][2]
----в полоску - 9,4,[0][1][2][4]
---синий - 5,2,[0][1][2]
---зеленый - 6,2,[0][1][2]
В php разбираем простенькой рекурсией, получаем все что нужно
"-" для наглядности вложенности
Поля: имя - id,parent_id,all_parents
-мячи - 1,0,[0]
--футубол - 2,1,[0][1]
---красный - 4,2,[0][1][2]
----в полоску - 9,4,[0][1][2][4]
---синий - 5,2,[0][1][2]
---зеленый - 6,2,[0][1][2]
--теннис - 3,1,[0][1]
---зеленый - 7,1,[0][1][3]
-груши - 8,0,[0]
Для выбора ветки "футбол"
select * from `table` where `id`=2 OR `all_parents` LIKE '%[2]%'
В ответ получаем всю нужную ветку
--футубол - 2,1,[0][1]
---красный - 4,2,[0][1][2]
----в полоску - 9,4,[0][1][2][4]
---синий - 5,2,[0][1][2]
---зеленый - 6,2,[0][1][2]
В php разбираем простенькой рекурсией, получаем все что нужно
Вы хоть представляете себе сколько времени всё это работает и какого нечеловеческого размера нужно дерево чтобы это было быстрее предложенного варианта?
слегка меняем принцип заполнения столбца all_parents - записываем туда id текущей рубрики. И лучше делать не массивом, а строкой. получаем запрос вида select * from table where all_parents like '[0][1][2]%', шлепаем индекс на all_parents (не скажу за MySQL, на PostgreSQL делается, хотя и довольно специфически) и все пашет очень даже быстро - запрос на выборку поддерева с 5 - 10 Килоузлами и вложенностью 8 - 10 занимает от 5 до 0.5 mc (5 - без кеширования, 0.5 - с внутренним кешированием БД).
От всех проблем на insert/update это не спасает, но заведомо быстрее nested sets.
От всех проблем на insert/update это не спасает, но заведомо быстрее nested sets.
Такой вариант уже чуть получше. Квадратные скобки излишни - достаточно одного разделителя. Но десериализация подобного дерева даст вам где-то те же 5ms - и вы будете иметь доступ ко всему дереву. В общем я бы стал использовать подобный подход для вариантов с несколькими тысячами узлов и тенденцией к увеличению их количества. Если же это, скажем, рубрики которые вам нужно отображать "кусочно", то ещё неизвестно что будет лучше (сколько времени будет обрабатываться запрос вида 'all_parents like "[0]%" or all_parents like "[0][1]%" ...' ? там же несколько раз придётся по базе пройтись), а уж по простоте написания вариант с деревьями в базе, а не в PHP точно проиграет...
Я ж говорю, не обязательно способ универсальный, все зависит от задачи. Но согласитесь, очень простое решение :) Я в то время знал mysql поверхностно (впрочем и сечас не сильно круто)
Эммм.. может быть стоит использовать Materialized Path ? Или я не в теме?
http://phpwiki.ru/Tree/Mp
http://phpwiki.ru/Tree/Mp
НЛО прилетело и опубликовало эту надпись здесь
nested sets - замечательная штука, пока не возникает задача вставки элемента куда-нибудь в серединку, или в начало такого дерева. или задача перемещения ветви такого дерева. Как только дерево мало-мальски разрастается, insert и update начинают вполне конкретно тормозить (у меня эффект начинал наблюдаться уже на 1500 узлах).
Nested sets идеально подходят для веба, в связи с тем, что там малое количество обновлений информации и много запросов на выборку. Doctrine кстати поддерживает nested sets (и не только) и сам делает всю черновую работу.
Nested sets не идеально подходят для веба. Единственный плюс - вывод дерева в правильном порядке одним запросом. На сравнительно больших ветвистых деревьях (25 - 30 КилоУзлов) выигрыш по сравнению с альтернативными алгоритмами (я не имею в виду рекурсию) - около 2 - 3 секунд. на небольших - значительно меньше.
Минусы - вставки и переносы. К примеру у нас есть древовидный форум - вроде текущего обсуждения, но с бошльшей интенсивностью - что-нить вроде обсуждения последнего апдейта яндекса на searchengines. Я пытаюсь добавить комментарий, к примеру, ко второму сообщению в таком обсуждении, всего сообщений 1000. При добавлении будет апдейт по крайней мере 998 строк таблицы. Я не скажу наверняка про MySQL (хотя мне приходилось чистать, что insert и update - не самые сильные его стороны), но PostgreSQL на подобных задачах начинает откровенно загибаться.
Правильнее сказать, что nested sets идеально подходят для деревьев, которые уже никогда не изменятся, либо все изменения будут происходить вне уже сформированных веток. На весь веб я бы не обобщал
Минусы - вставки и переносы. К примеру у нас есть древовидный форум - вроде текущего обсуждения, но с бошльшей интенсивностью - что-нить вроде обсуждения последнего апдейта яндекса на searchengines. Я пытаюсь добавить комментарий, к примеру, ко второму сообщению в таком обсуждении, всего сообщений 1000. При добавлении будет апдейт по крайней мере 998 строк таблицы. Я не скажу наверняка про MySQL (хотя мне приходилось чистать, что insert и update - не самые сильные его стороны), но PostgreSQL на подобных задачах начинает откровенно загибаться.
Правильнее сказать, что nested sets идеально подходят для деревьев, которые уже никогда не изменятся, либо все изменения будут происходить вне уже сформированных веток. На весь веб я бы не обобщал
как уже советовали Materialized Path и больше выдумывать нечего...
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Деревья в MySql/Php.