Внимание! Это задание - черновик.
Нужно оптимизировать работу хранилища под большие объемы данных и быструю работу с ними.
В документации к вашей реализации хранилища докажите, что асимптотики используемых вами алгоритмов удовлетворяют требованиям.
Пусть у JVM, в которой работает база данных, память ограничена в 64 МБ (это будет зафиксировано в тестах).
- Хранилище сможет содержать 100000 записей с ключами размером до 50 байт и значениями до 10 КБ
- Хранилище должно полностью сохранять свое состояние на диск после команды close()
- Хранилище должно быть потокобезопасным
- Амортизированная асимптотика вставки, удаления, изменения - не больше O(log n)
- Асимптотика чтения - не больше O(log n)
- Асимптотика повторного запроса на чтение того же ключа за короткое время - O(1)
- TODO гарантии по времени
- Избегайте чрезмерно частой работы с диском, особенно random seek'ов.
- Будет удобнее разбить базу данных на несколько файлов.
- Хранилище обязано полностью сохранять состояние на диск только по команде close(), значит, до этого имеет смысл не писать все изменения сразу на диск, а как-то буферизовать их.
- Все значения точно не влезут в память. А вот ключи могут.
- Возможно, формат файлов и алгоритмы чтения и записи стоит пересмотреть. Изучите, как работает LSM-Tree.
- Результаты, полученные при чтении, можно кешировать в памяти, на случай, если к ним обратятся повторно.
- Время на инициализацию хранилища условием не ограничено.