Задачка для размышления

[ruslan]

Уважаемые знатоки, с вами играет житель Сум. Предистория.

Предположим, есть некий каталог (товаров, ссылок - неважно). Размер и глубина вложености данного каталога неизвесна - может быть 3 уровня вложености при, скажем, 10 000 элементах; может быть 10 уровней вложености при 50 элементах в ощем, не знаем каков будет каталог ни по размеру, ни по глубине. Все это хранится в одной табличке, структура которой, скажем следующая: id, name, parent_id (по логике все понятно, что какое поле значит). В тоже самое время, каталог не есть постоянным, он все время растет... Опять же, как вширь, так и в глубину.

Внимание, вопрос.

Каким методом лучше воспользоваться для того, чтобы построить путь от текущего элемента к корневому: то ли рекурсивно запросами к БД (а если вложенность элементов 100?), то ли одним запросом считать все в хеш (а если кол-во элементов 1000 000?) и в нем уже найти полный путь? Или, быть может, еще каким-нибудь способом?

Время пошло...

 

[UFO.cz]

Ответ: Задачка для размышления

Я бы с многоуровневым каталогом копал в сторону nested sets

 

[ruslan]

Відповідь: Ответ: Задачка для размышления

Я бы с многоуровневым каталогом копал в сторону nested sets

Скажем так, структуру таблицы нельзя менять. Вот что по условию есть - то и имеем

 

[quant]

Відповідь: Задачка для размышления

всё что здесь описано в математике называется графом, а если быть точнее то это дерево - поможет при поиске решений
на счёт поиска корня, из описания "Предположим, есть некий каталог..." следует что корень один ... не совсем понятно что тогда искать ...
допустим нужно найти каталог опускаясь к корню, мне кажется лучшее решение это создать функцию в базе данных - я знаю точно в MySQL И в PostgreSQL это сделать можно и уже прямо в базе данных найти искомый каталог, можно обойтись без рекурсии - двумя циклами, а если индексы ещё и расположены по возрастанию то 1 циклом и вложенным бинарным поиском

 

[ruslan]

Відповідь: Задачка для размышления

из описания "Предположим, есть некий каталог..." следует что корень один ... не совсем понятно что тогда искать ...
допустим нужно найти каталог опускаясь к корню, мне кажется лучшее решение это создать функцию в базе данных - я знаю точно в MySQL И в PostgreSQL это сделать можно и уже прямо в базе данных найти искомый каталог, можно обойтись без рекурсии - двумя циклами, а если индексы ещё и расположены по возрастанию то 1 циклом и вложенным бинарным поиском

Никак нет, корень не один. Если это облегчит работу, то пусть наш каталог будет многоуровневым меню Хотя, о любом каталоге можно сказать, что корень, все-таки один - это нулевой родитель. Но на том же уровне масса может быть узлов с нулевым родителем. Хотя, это никак на задачу не влияет.
Про функции в БД: насчет MySQL, так они были введнены, кажется, с пятой версии. А если версия сервера 3.х? К тому же, по условию задачи нельзя трогать существующую структуру: нельзя ничего эдить, альтерить и криейтить.

 

[FEOFAN]

Ответ: Задачка для размышления

Мне кажется 100 000 быть не может. Но если уж на то пошло - я бы создал текстовый файл-кеш, в который бы запсиал сразу все пути.
А потом бы регэкспом или лучше даже str_pos выбирал ту строку, где заданный id последний и жухал бы ее сразу же на экран.
файл бы обновлял раз скажем в 5-10 минут, или по мере надобности. Мне кажетсмя такой подход вполне оправдал бы себя.

 

[Dre.hz]

Ответ: Задачка для размышления

You must be registered for see links

Однозначно вот это.

 

[Vladimir Smirnoff]

Ответ: Задачка для размышления

Каким методом лучше воспользоваться для того, чтобы построить путь от текущего элемента к корневому: то ли рекурсивно запросами к БД (а если вложенность элементов 100?), то ли одним запросом считать все в хеш (а если кол-во элементов 1000 000?) и в нем уже найти полный путь? Или, быть может, еще каким-нибудь способом?

Время пошло...

Кешировать результаты выборки к примеру по ADODB либо Zend db (по крону лучше всего) и рекурсивно строить дерево.
Еще, как вариант - вынести таблицу с товарами в sqlite файл. Будет то же самое, что советовал Феофан, только с удобными запросами.

 

[ruslan]

Відповідь: Ответ: Задачка для размышления

You must be registered for see links

Однозначно вот это.

Оно-то классно, не спорю, но возвожности модифицировать табличку нет. Три поля и все!

 

[Dre.hz]

Ответ: Відповідь: Ответ: Задачка для размышления

Оно-то классно, не спорю, но возвожности модифицировать табличку нет. Три поля и все!

Чего нет? Модифицируй как хочешь. Только оставь ID, Parent, Left и Right.