Без базы данных, даже без нескольких кардинально разных, такой проект невозможен. Поэтому немного посвящу времени этому вопросу.
Итак как минимум будет нужна БД обслуживающая обычные «плоские» данные – т.е. некоторому идентификатору ID ставится в соответствие поле данных.
Почему поле данных я рассматриваю одно? Потому что:
- выборка производится только по полю ID – поиск по данным не производится. Для этого есть специализированные индексы – иначе с такими количествами информации толку будет мало
- любое количество полей можно упаковать в одно, для этого я "на коленке" создал набор небольших прикладных библиотек, в частности при упаковке сохраняется CRC данных, чтобы не использовать не дай бог битые
Основными операциями для таких таблиц БД являются:
- выборка по ID
- прочитать последовательно всю базу (в память или хэш)
- обновить запись по ID
- вставить новую в конец, получить ID
Оптимальным я счел использование таблиц «страничного типа», где данные хранятся, пишутся, читаются с диска страницами. В каждой странице – фиксированное количество записей. Совсем просто если я заранее знаю фиксированный размер записи – тогда таблица будет работать еще быстрее, однако и в случае когда размер записи изменяется – существенно в обработке ничего не меняется. Обновление, добавление в конец делаются в рамках страницы в памяти, потом страница пишется на диск. В файле таблицы страницы хранятся последовательно.
Возникает вопрос как обновлять записи в середине таблицы когда их размер меняется – ведь если вся таблица больше 10-20-200 Гб, то скопировать половину таблицы во временный файл, а потом обратно будет занимать часы? Я переложил этот вопрос на файловую систему разбив все страницы на блоки. Один блок – один файл на диске, количество файлов одной таблицы не ограничено. В каждом файле хранятся последовательно ограниченное фиксированное количество страниц. Тогда если надо обновить запись в середине таблицы, то мне надо изменить только 1 файл гораздо меньшего и, зачастую, ограниченного объема.
Хорошо, с обычными таблицами решили. Сейчас описанная БД очень неплохо, в частности, обрабатывает в процессе поиска 35 Гб кусков текстов, с произвольной выборкой.
Но есть и ограничения – в такой таблице хранить соответствие: для каждого слова список документов в которых слово встретилось (вместе с дополнительной информацией) - практически невозможно – по каждому слову будет ну очень много документов, а соответственно и объем будет огромный.
Итак какие операции надо делать с такой БД:
· последовательную выборку с начала списка по нужному произвольному слову и пока не надоест
· по хорошему надо бы изменять список документов для слова, но тут можно сделать финт – обойтись только вставкой в конец БД
Как обновлять такой индекс? Очевидно что если индекс пустой и мы начнем в него вставлять списки документов начиная с первого слова и заканчивая последним – писать мы будем только в конец файла. Более того, писать или не писать физически отдельные блоки для каждого слова – отдельно на диск, дело разработчика – и в том и другом случае можно просто запомнить: где закончился очередной блок и его длину, сохранить это в простейший список. Тогда процедура последовательного чтения будет такая: перемещаемся в файле на начало списка для нужного слова, и читаем последовательно пока не начнется список для следующего слова: 1 seek, и минимально необходимое кол-во read - победа (здесь я специально не считаю операции самой файловой системы - можно отдельно заняться их оптимизацией)
Теперь, очевидно, когда мы хотим добавить в индекс информацию о ново проиндексированных страницах, можем скопить новую информацию отдельно, открыть текущий индекс для чтения, а новый создаваемый на запись, и читать-писать последовательно сливая с информацией которую надо добавить, начиная с первого слова и заканчивая последним. Вопрос о том, в каком порядке складывать в список документы я рассмотрю чуть позже.
Комментариев нет:
Отправить комментарий