Древовидные струткуры в базе данных с частым insert(+)

[Sherman]

Древовидные струткуры в базе данных с частым insert(+)

Собственно задача возникла такая:

Нужно в бд(mysql) хранить древовидную струткуру(подобие файловой системы), объем данных очень приличный(может достигать нескольких миллионов записей).

Операции вставки и выборки, а также удаления проходят довольно часто, поэтому nested sets мне не подходит, ближе наверное классическая структура child-parent, но очень не хочется ее использовать, т.к. при выборке это большая нагрузка(тут ведь рекурсия нужна будет).

Вопрос:

Есть ли какие-либо алгоритмы для таких задач(с использованием СУБД и SQL) или же нужно писать подобие своей собственной СУБД?

 

[Фанат]

Вот конец исследования su1d по этому вопросу.
http://www.livejournal.com/users/demiurg/53125.html
остальное там радом должно быть.

 

[Sherman]

Ну вобщем, как я и предпологал чуда не бывает, видимо придеться вспоминать суровый c++ и лабать все на файлах

 

[SelenIT]

классическая структура child-parent... при выборке это большая нагрузка(тут ведь рекурсия нужна будет

Можно всю "грязную работу" переложить на плечи самой MySQL. Несколько примеров здесь: http://forum.dklab.ru/php/heap/HierarchicalStructuresInADb.html.

 

[Sherman]

Ну это не выход в моем случае, т.к. вложенность может быть запросто больше 50, открою секрет — это поисковый механизм по файлам, ftp, smb и т.д.

 

[alexhemp]

Sherman
А часто ли тебе потребуется строить полные пути?

Можно попробовать гибридный вариант. При индексации использовать быстрый на вставки Adjacency List а потом генерировать "индекс" для выборки на базе Nested Sets.

Поскольку в поисоковой системе быстрый поиск - это важно, вполне допустимы вспомогательные индексы.
Опять-же - миллионы записей - это скорее всего выделенный сервер, так что индексацию можно написать и на С

 

[3BEP]

Sherman
А может лучше обойтись без древовидной структуры и хранить в одной строке, например, имя севера|путь относительно корня сервера|имя файла?

 

[Bred Vilchec]

Sherman
Просто добавь поле level и максимальная вложенность будет - уссаться можно, а именно, насколько это позволит твоя версия MySQL. Мне лично концепция Котерова (ссылку давал SelenIT) не очень понравилась как раз из -за таких вот случаев: писать запросы под максимальную вложенность в 100 не красиво когда на самом деле она будет, например, 10. И с другой стороны, нельзя предполагать, что макс. вложенность будет не больше 50, ведь ХЗ в какую сторону и с какой силой проект будет расти.
Если идея с переложением грязной работы на БД все же окажется жизнеспособной, может имеет смысл какой-нить класс для удобства работы с ней написать, я подумаю.
Сорри за оффтоп, но этот подход мог бы быть особенно хорошим, если использовать UDF, в других БД это дело вроде сподручнее, я не знаю...

 

[Sherman]

Полные пути может быть и не так часто, а вот ветки строить придеться — это точно. Если же отказать от структуры дерева, то тогда не будет возможным работа в режиме просмотра сервера. Т.е. перемещение по его каталогам. Тут еще задача не полностью сформулирована

 

[alexhemp]

Sherman

Почему не возможна? Можно строить каталог строковыми операциями, нужно поэкспериментировать, если скорость устроит, то и нормально. Все зависит от количества файлов на одном сервере.

 

[Bred Vilchec]

alexhemp и 3BEP - извращенцы...

 

[3BEP]

Sherman
Тогда тебе подойдет вариант кеширования пройденного пути в режиме просмотра или хранение в дополнительном поле пути к каталогу от корня сервера (будет всего два запроса - получить инфу о текущем каталоге и выбрать еще одним запросом всю информацию о предках)

Добавлено
Кстати, максимальноя вложенность не превышает 128 (один символ на имя каталога + "\" при такой вложенности достигнут 255)

 

[Sherman]

Про вложенность не понял...предел чего?

 

[Bred Vilchec]

прибейте зверюгу...

 

[alexhemp]

Bred Vilchec

Может прекратишь флудить? Говори по делу.

-~{}~ 15.06.05 14:22:

Sherman
Вероятно 3BEP имеет ввиду максимальную вложенность каталогов. Но я бы не закладывался на то, что она будет 128. Но 128 это очень много...

 

[Bred Vilchec]

alexhemp
У меня такое ощущение, что мои слова больше относятся к делу чем призывы хранить полный путь в строке и "строить каталог строковыми операциями". А "один символ на имя каталога" - эт ваще шедевр.

Sherman
Вот-вот, сформулируй сначала задачу более точно. Что-то мне кажется, что в поисковой системе запросы на вставку и удаление данных весьма редки относительно запросов на выборку. + еще раз с толком и расстановкой расскажи про типовые запросы, например, как я понял, это выборка всех
нодов данного каталога, что еще?

 

[alexhemp]

Bred Vilchec

Про строить каталоги строковыми операциями.
Нужно тестировать. Если число файлов на сервере небольшое, то сгруппировать по подстроке до первого слеша может быть достаточно быстро.
Все зависит от масштабов, а решение простое и при небольшом числе файлов может отлично работать.

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

 

[Sherman]

Главная трудность это выбрать как строить индекс, индекс это самое сложное на данный момент.

Про удаление/вставку — перестройка индекса 2 раза в сутки для активных сервером это норма.

Поиск хотелось бы сделать не полнотекстный, т.е. чтобы можно было искать по маске.

Задача:

Поиск по фтп/файлам/smb/etc - серверам.

Броузер по серверам.

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

Сейчас вопрос стоит в том: как хранить информацию(читай индекс).

 

[3BEP]

Sherman
Как будет происходить перестройка индекса?
скрипт будет проходить по уже существующему индексу и сравнивать его с сервером? или для сервера индекс будет сбрасываться и строиться заново?

 

[Sherman]

Конечно второй вариант. Т.к. это, в среднем случае, будет менее затратно, имхо.