Организация древовидной структуры в CMS и скорость работы

[LeZZvie]

Организация древовидной структуры в CMS и скорость работы

Столкнулся сейчас с самой популярной проблемой - организовать древовидную структуру в MySQL для CMS.
Поюзал поиск. Наткнулся на мессагу от Фаната:

лично я в форуме пишу в каждую запись весь путь к ней.
все дерево выводится простой сортировкой.
в какой-то из статей такой способ точно описывается.

Уважаемый Фанат. Можно как-то поподробней про этот способ?

И еще:
с базами данных на таком уровне мне работать приходилось до этого очень редко.
Обычно просто добавить-удалить-изменить. Что не вызывало особых проблем...

Если делать стандартными способами дерево - то не могу вкурить, почему почти все юзают поля типа right и left
для таблицы? Т.е. понятно что отслеживают уровень. Но почему сразу в двух направлениях?

 

[Alexandre]

Если делать стандартными способами дерево - то не могу вкурить, почему почти все юзают поля типа right и left
для таблицы?

есть несколько способов хранения дерева, один из них
http://phpclub.ru/detail/article/2002-06-03
http://phpclub.ru/detail/article/db_tree
есть преимущества и недостатки при хранении в таком виде, все зависит от того что нужно.

 

[Фанат]

древовидные структуры бывают двух видов - простая и сложные.

простая - это когда в записи содержится только идентификатор родителя, и ничего больше.
Это наиболее простая и понятная форма. запись добавляется одним инсертом. для того, чтобы переместить элемент дерева, достаточно сменить у него идентификатор родителя. причём - только у него одного. все его дети переедут вместе с ним.

У этого подхода есть один недостаток - построение дерева производится только с помощью рекурсии. то есть, сколько элементов в дереве (или его ветке) - столько [запросов] мы делаем. То есть, для большого ветвистого дерева этот вариант неприемлем.

И поэтой причине существует очень много реализаций сложных деревьев. Которые могут построить ветку одним запросом. (Это не касается базы данных оракл. там есть оператор CONNECT BY, который строит дерево одним запросом по базе простой формы)

Но. есть один нюанс. На нормальном сайте не бывает много разделов. Максимум несколько десятков. При таком подходе даже несколько вложенных запросов не будут напрягать базу, а если выбирать все разделы одним запросом, то тогда нагрузка и вовсе станет смехотворной.
Именно по этой причине я стою за простую структуру для CMS сайта.

Важное замечание. Не надо путать структуру сайта со структурой разделов. Если на сайте есть е-магазин с тыщей каталогов - это отдельный раздел. не надо путать структуру МАГАЗИНА и структуру САЙТА. И не надо их валить в одну базу только потому, что принцип уних одинаковый - дерево. У стрраницы "Наши координаты" нету ни цены, ни наличия на складе.

-~{}~ 15.01.07 22:08:

Странно. что-то за весь вечер никто и не пнул...

 

[Popoff]

простая - это когда в записи содержится только идентификатор родителя, и ничего больше.

Эта форма называется "списки смежностей", или, по-английски, "Adjacency Lists". Термины описаны в словаре.

Фанат, запутаешь ребёнка, а он потом будет искать в гугле "простая форма хранения дерева" и удивляться.

У этого подхода есть один недостаток - построение дерева производится только с помощью рекурсии. то есть, сколько элементов в дереве (или его ветке) - столько [запросов] мы делаем.

1. количество запросов можно значительно уменьшить, если воспользоваться соединением таблиц самой на себя. Если глубина дерева не очень большая, то выборка всех родителей, к примеру, решается даже в один запрос. Способ предложен господином Котеровым, если я не ошибаюсь.

2. Количество запросов, даже если не использовать соединение на себя, думаю, немного преувеличено.

3. Мы можем построить дерево с использованием вложенных множеств, там будет всегда ровно один запрос, но время выполнения может быть как меньше, так и больше, в зависимости структуры и размера дерева. В особенности на больших деревьях интересные эффекты получаются. Почему-то многие считают количество запросов, но мало кто меряет время.

И поэтой причине существует очень много реализаций сложных деревьев. Которые могут построить ветку одним запросом.

Традиционными являются два из них - вложенные множества и материализованные пути. Если покопать, можно найти ещё много разных, но они, думаю, имеют скорее теоретический интерес, по карйней мере на данном этапе.

лично я в форуме пишу в каждую запись весь путь к ней.

Этот способ называется "Материализованніе пути".

организовать древовидную структуру в MySQL для CMS

лично я в форуме пишу в каждую запись весь путь к ней.

То ж в форуме. А то в CMS. Там разные деревья, у них разная структура, с ними нужно делать разные операции. Способ с материализованными путями хорошо может подойти для древовидного форума, но плохо подходит для средней стандарной CMS.

+1 за списки смежностей.

 

[Фанат]

ой, забыл написать! то, ради чего так долго распинался!
Главное, отредактировать даже зашёл, и опять забыл =)

Короче. Для случая структуры сайта, с парой десятков разделов, все делается, как раз, одним запросом! Просто вытягиваются из базы все разделы, на каждой странице, одним запросом.
разбираются в иерархическую структуру скриптом, и потом используются для построения меню, навигации и всего прочего.

Popoff
спасибо за цуенные замечания. как-то я да - все лапидарно написал очень.

 

[Popoff]

А, да. Не дочитал.

Если делать стандартными способами дерево - то не могу вкурить, почему почти все юзают поля типа right и left

Этот способ называется "Вложенные множества". Вложенные множества не являются более стандартными, чем списки смежностей. Скорее даже наоборот. Списки смежностей - это классический, можно даже сказать, древний, проверенный, хорошо зарекомендовавший себя способ. А вложенные множества были придуманы (или по крайней мере стали широко известны программистам) гораздо позже списков смежностей.

 

[LeZZvie]

Спасибо за подробные ответы!
Пошел читать )