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

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

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

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

ЗЫ. Модераторам: если тема не подходит для раздела - перекиньте, куда нужно :) Спасибо.

Да, когда я услышал про гигабайты XML, то чуть не заплакал...

Хм, я с удовольствием уговорю заказчика использовать внешнюю БД для хранения индекса, если к ней есть биндинги из Java. Мне самому велосипед делать не особо хочется.
Подскажите, на какие БД лучше всего посмотреть? Критерии: GPL, быстрое выполение INSET, SELECT. Не особо важен UPDATE. Хранение больших объемов данных - несколько гигабайт. И чтобы это не съедало всю производительность компа :)