До сих пор все было отлично, но как нам прежде

Question

До сих пор все было отлично, но как нам прежде

всего отсортировать данные по
ключу? Входящие операции записи могут производиться в любом порядке.
Поддержание отсортированной структуры на диске возможно (см. подраздел
«B-деревья» текущего раздела), но гораздо проще будет делать это в оперативной памяти. Существует множество доступных для использования хорошо
известных древовидных структур данных, например красно-черные деревья или
AVL-деревья [2]. При использовании этих структур можно вставлять ключи в любой
последовательности и затем читать их в нужном порядке.
Теперь мы организуем работу нашей подсистемы хранения следующим образом.
При поступлении записи добавляем ее в располагающуюся в оперативной памяти сбалансированную структуру данных (например, красно-черное дерево).
Это располагающееся в оперативной памяти дерево называется MemTable
(от memory table — «таблица, расположенная в памяти»).
Когда размер MemTable превышает определенное пороговое значение — обычно несколько мегабайт, — записываем его на диск в виде файла SS-таблицы.
Эта операция выполняется достаточно эффективно, поскольку дерево поддерживает пары «ключ — значение» в отсортированном по ключу виде. Новый файл
SS-таблицы становится последним сегментом базы данных. А пока SS-таблица
записывается на диск, операции записи продолжают выполняться в новый
экземпляр MemTable.
Для обслуживания запроса на чтение сначала пробуем найти ключ в MemTable,
затем в последнем по времени сегменте на диске, затем в предпоследнем и т. д.
Время от времени запускаем в фоне процесс слияния и уплотнения, чтобы объединить файлы сегментов и отбросить перезаписанные или удаленные значения.
Представленная схема работает отлично. У нее есть только одна проблема: если
происходит фатальный сбой БД, то записанные позже всего данные (находящиеся
в MemTable, но еще не записанные на диск) теряются. Чтобы избежать этой проблемы, можно держать на диске отдельный журнал, в конец которого немедленно
добавляются все записываемые данные, точно так же, как в предыдущем разделе.
Сам журнал неупорядочен, но это неважно, ведь его единственное назначение —
восстановление MemTable после сбоя. Всякий раз, когда MemTable записывается
в SS-таблицу, соответствующий журнал можно удалять.