Задача: библиотека мини-базы данных

Описание

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

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

Задача 1

Функциональные требования

Библиотека должна предоставлять пользователю следующие возможности:

1. Создание новой базы данных (одного или группы файлов со специфическим форматом).
2. Сохранять пользовательские данные, заданные в виде ключ/значение в указанной базе данных.
3. Библиотека должна осуществлять поддержку следующих типов для использования их в качестве ключей и значений:
   • знаковое целое
   • строка
   • произвольные пользовательские данные, поддерживающие операцию serialize()
4. Удалять элемент базы данных по указанному ключу.
5. Предоставлять пользователю сохраненные данные, используя указанный ключ.
   В случае, когда ожидаемая запись – пользовательский тип данных, восстановление из базы данных должно быть возможно при наличии у пользовательского класса операции deserialize().
6. Предоставлять возможность навигации (итерации) по всем сохраненным данным.

Требования к эффективности

Замечание: тот факт, что данные должны храниться на внешнем носителе (при посредничестве файловой системы) говорит о том, что гарантии эффективности тех или иных операций предоставить невозможно. Этот раздел накладывает ограничения только на используемые алгоритмы.

1. Вычислительная сложность открытия существующей базы данных должна быть не более чем N * log N.
2. Вычислительная сложность получения данных по заданному ключу должна быть не более чем логарифмической.
3. Операция возвращения следующего элемента (при итерации по всем элементам базы данных) должна обладать постоянной скоростью.
4. Ограничений по эффективности на операции создания новой базы данных, помещения и удаления данных не накладывается.

Замечания по реализации

В качестве основы для реализации задачи предлагается использовать библиотеку Berkley DB.
Вместо Berkley DB можно использовать любую другую, которая удовлетворяет следующим условиям:

1. Используемая библиотека не решает непосредственную задачу.
2. Библиотека достаточно мобильна (т.е. работает, по крайней мере, на платформах Unix и Windows).
3. Библиотека не имеет лицензионных ограничений, которые бы не позволяли ее использование в учебных проектах.

Требования к проекту

Проект должен включать следующую пользовательскую документацию:

• инструкция по сборке и установке;
• описания программного интерфейса библиотеки;
• рабочий пример использования библиотеки.

Задача 2

Данная задача предполагает введение следующих новых возможностей в реализацию первой:

1. Поддержка возможности использования нескольких объектов, работающих с одной и той же базой данных как внутри одной нити исполнения так и в нескольких.
2. Поддержка транзакций.
3. Блокирование базы данных на уровне записей.

Следующий код (или функционально эквивалентный ему) должен работать правильно.
typedef Db<int, std::string> MyDb; MyDb db("my_db"); db.insert(20, "Initial value"); Db::element el = db.find(20); assert(el != db.end()); el.lock(); *el = "Changed value"; MyDb db1("my_db"); Db::element el1 = db.find(20); assert(el1 != db.end()); assert(*el1 == "Initial value"); el.commit(); assert(*el1 == "Changed value");