Дратути, меня зовут модест...
Есть хранилище: большой файл, разделённый на страницы (4...16Кб).
В хранилище лежит 100500 объектов переменной длины: в каждой странице 100...300 штук, в зависимости от их длины. Объекты хранятся в порядке их добавления в хранилище. Кончается текущая страница, открывается новая (в старой ставится ссылка на новую) и т.п. Страница пишется атомарно благодаря double-write-buffer как в InnoDB.
Разыскивается алгоритм и структура данных, которая бы позволяла сохранить информацию о порядке следования (списке) объектов. От структуры данных требуются операции:
1. Выдать N объектов с заданного смещения в списке
2. Атомарно переставить любой объект из его текущей позиции в начало списка (типа «поднятие топика»)
3. Операцию 2 выполнить в минимальное количество записей страниц, в деале за 1. У меня есть решение для 4 записей страниц на такую операцию, при этом между записями каждой страницы можно упасть и хранилище останется консистентным, но с учётом double write buffer реальных записей уже 8, а это 128 КБ записи на диск: дохрена для примитивной операции )
B-tree знаю как работает, но оно мне не нужно, я не хочу полноценное удаление-добавление-по-ключу, хочется проще и дешевле, не хочется полу-заполненных страниц, сплитов, мёрджей... Допустимо хранение всего индекса в памяти (но не самих объектов).
Варианты:
1. В каждый объект запилить поле «timestamp» (свежесть). Когда объект надо поднять в начало списка, то делаем touch этому timestamp. Это позволит на каждое поднятие объекта перезаписывать только ту страницу, где лежит этот объект. Недостаток: при холодном старте хранилища придётся прочитать ВСЕ объекты, чтобы построить индекс в памяти (дерево) по ключу timestamp. Хотя можно хранить массив timestamp объектов отдельно от самих объектов, в параллельном «потоке» страниц. Тогда при подъёме нужно читать меньше страниц.
2. Заюзать журнал и ссылки в объектах (двусвязный интрузивный список объектов). При поднятии объекта в начало списка, кидать в журнал команду, которая меняет ссылки между объектами. Вместо операции на реальных страницах просто кидать команду в журнал, таким образом пишется только 1 страница (страница журнала). Когда журнал набирает критическую массу, он накатывается на реальные страницы (но тут наступает необходимость перезаписать много разных страниц, хотя если список сделать не интрузивный, то есть prev-next (указатели) не хранить внутри самих объектов, а в отдельном «потоке страниц», то многие модификации указателей будут попадать на одни и те же страницы, в которых лежат эти указатели, поэтому количество страниц с указателями надо будет записать сильно меньше, чем самих указателей...).
Кастую DBMS-девелоперов и коммитчиков патчей в мускуль.
