Оптимизированный поиск по базе

[MIT]

Хотелось бы узнать как праильно организовать хранение текстовой базы данных для последующего поиска по ней. Просто есть программа (название не скажу - только в личку), которая производит поиск по >500 гиговой базе за минуту - две. Интересует именно теория (хотя и код не помешает) кэширования данных и их хранения. Субд пока не предлогать.

[ANDLL]

Вычисляется хэш и строится индекс, отсортирвоанный по хэшу.
Врям поиска = время вычисления хэш-кода + log(n) + время на сравнения m строк в случае коллизии
Если же время на операцию вставки совсем не имеет значения - то просто хранят строки в остортированном виде. Время поиска - не больше log(n)*(сравнение двух строк)

[MIT]

Ну, давай будем поближе к программированию. Возьмем простенькую структуру, в которой есть название, описание и прочие данные, которые нас не интересуют; описание намного больше названия. Все это дело хранится на жестком диске. Поиск надо производить либо по названиям, либо по описаниям.
Первая мысль - загнать все в оперативку и искать с помощью Array.Find (или чего-то подобного). Но! При этом в память грузится и пока не нужная информация, да и если вся база занимает большой объем, то и оперативки будет использоваться соответственно много.

Мысли: грузить в память только структуру, содержащую необходиые данные; грузить не все сразу, а по, например, 1000 штук; изначально как-то отсортировать данные.

Правильно я мылсю?

[ANDLL]

Думаю нет.
Для начала придумай, как ты свое дело будешь хранить в файле. И исходя из этого работай с ним, загружая(по одному, а не по 1000) только то, что нужно.
Когда речь идеть о поиске в сортированном массиве нет никакого смысла загрузить 1000 или 10000 элементов - из них все равно с большой степенью вероятности понадобится только один

[MIT]

Исходя из знания, что обращение к жесткому диску происходит медленнее, чем к оперативке и появляется идея загрузки какого-то куска бд в память. Но при этом все не загрузишь - вот тебе и проблема. Думаю, что базу следует разбить на таблицы первичной и вторичной важности, где первичные хранят данные, по которым осуществляется поиск, а вторичные, соответственно все остальное.
Собственно, вопрос и возник перед началом проектирования бд, чтоб потом все переделывать не пришлось за профнепригодностью.
Для меня, на данном этапе, структура хранения представляется всьма смутно, и ее воплащение упирается лишь в незнание системы поиска по базам, и в этом то и состоит основная задача.
Как правильно хранить данные? Как их правильно, оптимально и ресурсоэкономно обрабатывать (под обработкой я понимаю изменение/удаление/добавление элементов и поиск по ним)?

[tyomitch]

А критически важно набить все шишки самому, и не воспользоваться ни одной из существующих СУБД?

[MIT]

На данном этапе - да. Просто хочется понять, действительно ли все так безнадежно.
Просто изучение какой-либо СУБД займет довольно большой период времение (хотя, признаю, что изучать все равно придется), а сделать свое, при знании системы хранения - пару недель (+/-)

[ANDLL]

Госпаде MIT
То что сказано в начале(сортированный массив) относилось к быстрому поиску, а не к вставке и удалению.
Ты в конце концов определись что именно нужно.
Вообще переизлагать теорию здесь нет смысла. Есть, к примеру, трехтомник Кнута(из них второй том правда можно не читать, так как он целиком посвящен целочисленным методам), в котором описаны базовые компьютерные алгоритмы. Полагаю имеет смысл тупо отослать к нему.

[tyomitch]

Обалдеть, оказывается в ушедшем году вышел четвёртый том Кнута!

Автору: в том, что напишешь за две недели, будешь баги выискивать ещё полгода. Плюс твой подход немасштабируемый: на каком-то этапе захочется что-нибудь, что в СУБД уже есть, а тебе займёт ещё столько же времени на реализацию. (Скажем, сортировку.)

[MIT]

То что сказано в начале(сортированный массив) относилось к быстрому поиску, а не к вставке и удалению.

Вставка и удаление - это к структуре хранения. Собственно вопрос и не изменился: как искать и как хранить для оптимального поиска.

Ты в конце концов определись что именно нужно.

Нужна теория-описание, в которой изложены принцыпы поиска в бд.

Полагаю имеет смысл тупо отослать к нему.

Отошли (ссыль?)

Автору: в том, что напишешь за две недели, будешь баги выискивать ещё полгода. Плюс твой подход немасштабируемый: на каком-то этапе захочется что-нибудь, что в СУБД уже есть, а тебе займёт ещё столько же времени на реализацию. (Скажем, сортировку.)

Вообще-то, ты прав, немасштабиремость - плохо. Но все же хочется придти к пониманию вопроса. Все же склоняясь к изучению СУБД полезно и знание построения, например для использования поиска по большим коллекциям или массивам структур и/или построения баз с фиксированным функционалом.

[ANDLL]

http://www.ozon.ru/context/detail/id/3569851/
Меньше 300 рублей? Даа, как то у нас не ценят такие вещи...

[ANDLL]

Отошли (ссыль?)

http://www.google.ru/search?hl=ru&newwi ... =&aq=f&oq=
http://www.google.ru/search?hl=ru&newwi ... =&aq=f&oq=

Вставка и удаление - это к структуре хранения

В той же мере, что и поиск.

Вообще идея такая - в файле выделяется две области - место под индексы и под кучу данных. Индекс - это некоторая структура с операцией "найти" и "перестроить". Для примера - простейший индекс это просто отсортированные хэши строк.
Область данных это heap - некая структура с операциями "удалить" и "выделить место под x".
Единнообразного решения на тему как организовывать первый и второй нет.
Какими порциями подгружать из файла в память - вопрос сложный, но его можно и не решать - для простоты грузи строго по мере необходимости.

[MIT]

Зато остальные тома под 1000...
Кстати, год выпуска 4ого тома - 2007

Книжку щас на скачку поставил, почитаю... Может попозже и куплю даже.

[ANDLL]

Дописал предыдущий пост

[Ramzes]

А что общего эта темя имеет с Visual Basic.Net

[tyomitch]

Кстати, год выпуска 4ого тома - 2007

Подчастей 3 и 4 -- да.
Вторая переведена в 2008, нулевая вышла в 2008.
Первую планируют издать в 2009.

[MIT]

общего с .net - ориентировка именно на эту платформу, в связи с чем я и вспомнил коллекции и array.find.
2ANDLL: спасибо за инфу... короче надо упорно читать, понятно.