Как btree хранится на диске?

Question

Я знаю, как реализовать btree в памяти, но не ясно, как хранить btree на диске. Я думаю, что есть два основных различия:

1. Преобразование между указателем памяти и адресом диска, см. post .
2. Как разделить страницу при вставке нового элемента k / v? Это очень легко реализовать в памяти.

Спасибо

Answer 1

все зависит от используемой вами СУБД. Если вы хотите знать, как это реализовано в MS SQL Server, вам нужно прочитать следующее:

• Страницы (я думаю, они есть почти во всех современных СУБД) - в SQL Server они имеют размер 8 КБ. Файл базы данных составлен из страниц.
• Экстенты - логические группы из 8 непрерывных страниц
• (S) GAM - (общая) карта глобального распределения. Растровое изображение, содержащее информацию о свободных и занятых экстентах. Это одна из первых страниц файла базы данных.
• IAM - Карта распределения индекса. Вы можете узнать, в каком экстенте хранится индекс / куча. Имея эту информацию, вы можете попасть в файл, где хранится индекс / куча.

Используя IAM и GAM (или SGAM), вы можете разделить страницу - просто переместите часть страницы (которая должна быть переполнена) на другую страницу в файле.

IAM и GAM также являются ответами на ваш первый вопрос.

Большинство этих имен взято из MS SQL Server, но я вполне уверен, что в других СУБД это решается аналогично.

Надеюсь, это поможет.

Answer 2

Я рекомендую взглянуть на книгу Внедрение системы баз данных "

Глава 2 «Хранение данных» и глава 3 «Представление элементов данных» дадут вам несколько советов по этой проблеме.

В главе 4 структуры индекса есть раздел, посвященный Btrees

Это лучший источник информации, которую я нашел на данный момент по этой теме.