Требуется создать свой движек БД. Задача - быстрый поиск/добавление данных в таблицу. Количество таблиц небольшое, зато объем данных значительный - гигабайты. Индексируем много текстовой информации. Из таблиц пока - словарь со словами в нормальной форме и таблица файлов, в которой содержится информация обо всех проиндексированных словах, принадлежащих файлу.
Прошу помощи по информационному и математическому обеспечению :)

Где почитать о том, какие существуют структуры данных для хранения информации и быстрого к ней доступа? А также какие наиболее эффективные алгоритмы поиска по таким структурам?
Можно на английском.

Другая проблема - заказчик почему-то настаивает на XML - как формате для хранения проиндексированных данных и словаря. Я в шоке, представляю сколько места ЭТО будет занимать на диске и сколько времени обрабатываться парсером...
Хм, на мой взгляд, намного логичнее хранить словарь и список файлов в бинарном формате. Вот только, чтобы ему это доказать аргументированно, мне нужно побольше почитать про форматы хранения и алгоритмы поиска.

Помогите пожалуйста :)

PS. Или забить на все это и воспользоваться готовой БД, вроде Oracle Text и Berkeley DB ? Тогда порекомендуйте какую использовать! Требования: GPL, быстрое выполение INSET, SELECT. Не особо важен UPDATE.

Да и я о том же думаю. Какой вот сервер подобрать? BDB, mysql, postgres?