Реализация ранжированных запросов с деревьями B+ и изоляцией моментальных снимков
Я разрабатываю новый продукт для сервера баз данных NoSQL. Есть ли какие-либо документы о том, как реализовать диапазонные запросы на кластерных деревьях B+, использующих изоляцию моментальных снимков?
2 ответа
Я написал пару реализаций дерева B+. Для запроса диапазона вы перемещаете курсор на клавишу с нижней границей диапазона, затем "двигаетесь вправо", пока не достигнете верхней границы. Дерево B+-связи (с указателями влево / вправо между конечными узлами) делает это чрезвычайно простым.
Я, однако, никогда не реализовывал изоляцию моментальных снимков. Я думаю, что это сильно зависит от вашего алгоритма изоляции. Если вы используете теневые страницы (где вы создаете копии измененных страниц для каждой транзакции), то вам нужно проверить, существует ли теневая страница, прежде чем "двигаться вправо" по конечным узлам.
Вы можете добавить скрытый столбец в каждую строку с именем "RowVersion". Всякий раз, когда вы обновляете строку, вы вставляете новую строку, а RowVersion обновляется до текущего номера транзакции. При чтении вы берете ту строку, у которой самая низкая версия>=, чем номер вашей транзакции. Вам также понадобится какая-то задача по очистке.
Вы также можете сохранить версию строки в другом месте. Это не обязательно должно быть в одном и том же B-дереве. Вы можете хранить их в оперативной памяти или во временной базе данных, которая воссоздается при перезапуске сервера.