История изменений

Но для моей операции мне понадобится выдернуть ключ и вставить новый ключ, причём возможно с выделенеим новых страниц. Это будет запись минимум 2 страниц — ту, из которой ключ убили + ту, куда добавили. А ещё может быть, что нужно выделить ещё одну.

Это всё

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

Дерево будет дырявое и потребляющее новые страницы (если ключом будет timestamp изменения объекта).

Дырявость всегда ограничена сверху, оно не может вырасти за вполне определённые размеры. У тебя же дырявость и так имеет мето быть из-за вытаскивания некоторых объектов и эта дырявость будет отбирать значительно больше места. Вроде эта проблема более важная чем организация индекса.

Хотя казалось бы, что задача звучит просто: список, выдернуть, положить наверх. Хочется поискать что-нибудь проще B+-tree.

Отдельный список проще. Если не нужно чтобы первый пункт отрабатывал быстрее чем за O(skip + N), то это самое простое решение. Его тоже можно сделать на страницах и дампить только грязные.

Но для моей операции мне понадобится выдернуть ключ и вставить новый ключ, причём возможно с выделенеим новых страниц. Это будет запись минимум 2 страниц — ту, из которой ключ убили + ту, куда добавили. А ещё может быть, что нужно выделить ещё одну.

Это всё

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

Дерево будет дырявое и потребляющее новые страницы (если ключом будет timestamp изменения объекта).

Дырявость всегда ограничена сверху, оно не может вырасти за вполне определённые размеры. У тебя же дырявость и так имеет мето быть из-за вытаскивания некоторых объектов и эта дырявость будет отбирать значительно больше места. Вроде эта проблема более важная чем организация индекса.

Хотя казалось бы, что задача звучит просто: список, выдернуть, положить наверх. Хочется поискать что-нибудь проще B+-tree.

Отдельный список проще. Если не нужно чтобы первый пункт отрабатывал быстрее чем за O(skip), то это самое простое решение. Его тоже можно сделать на страницах и дампить только грязные.