Реализация ранжированных запросов с деревьями B + и изоляцией моментальных снимков

Question

Я занимаюсь разработкой нового продукта сервера баз данных NoSQL. Существуют ли какие-либо документы о том, как реализовать диапазонные запросы на кластерных деревьях B +, использующих изоляцию моментальных снимков?

Answer 1

Я написал пару реализаций дерева B +.Для запроса диапазона вы перемещаете курсор на клавишу с нижней границей диапазона, затем «двигаетесь вправо», пока не достигнете верхней границы.Дерево B + -линков (которое имеет левые / правые указатели между конечными узлами) делает это чрезвычайно простым.

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

Answer 2

Вы можете добавить скрытый столбец в каждую строку с именем «RowVersion».Всякий раз, когда вы обновляете строку, вы вместо этого вставляете новую строку, а RowVersion обновляется до текущего номера транзакции.При чтении вы берете ту строку, у которой самая низкая версия> =, чем номер вашей транзакции.Вам также понадобится какая-то задача очистки.

Вы также можете хранить версию строки в другом месте.Это не обязательно должно быть в одном и том же B-дереве.Вы можете хранить их в ОЗУ или во временной базе данных, которая воссоздается при перезапуске сервера.