Как хранятся данные: страницы и файлы

Серия про транзакции закончилась восстановлением после сбоя, и там всё упиралось в одно: что лежит на диске, а что только в памяти. Пора открыть этот ящик. В уроке про архитектуру СУБД внутренний уровень был складом, о котором приложение ничего не знает. Этот урок про то, как склад устроен: из каких файлов состоит таблица, почему СУБД читает диск кусками по 8 КБ и зачем ей собственный кэш в памяти.

Склад и коробки

Представь склад интернет-магазина. Кладовщик не носит товары по одной штуке: он берёт с полки коробку целиком, приносит к столу и уже там достаёт нужную вещь. Поход к полке долгий, а коробка в руках почти ничего не стоит. Поэтому выгодно, чтобы вещи, которые часто нужны вместе, лежали в одной коробке.

СУБД работает с диском так же. Она не читает с диска одну строку. Она читает целый блок фиксированного размера, и такой блок называют страницей. В PostgreSQL страница занимает 8 КБ. Нужна одна строка таблицы students? СУБД загрузит всю страницу, на которой эта строка лежит, вместе с соседями.

Таблица это файл из страниц

На диске таблица хранится обычным файлом в каталоге данных СУБД. Файл разрезан на страницы одинакового размера: страница 0, страница 1, страница 2 и так далее.

файл таблицы students
┌──────────┬──────────┬──────────┬──────────┐
│ стр. 0   │ стр. 1   │ стр. 2   │ стр. 3   │  ...
│ 8 КБ     │ 8 КБ     │ 8 КБ     │ 8 КБ     │
└──────────┴──────────┴──────────┴──────────┘

Строки таблицы разложены по этим страницам. Каждая строка получает адрес: номер страницы плюс номер места на странице. Зная адрес, СУБД читает ровно одну страницу и сразу находит строку.

Когда страницы заканчиваются, файл растёт: в конец дописывается новая пустая страница. В PostgreSQL файл таблицы режется на куски по 1 ГБ, чтобы не упираться в ограничения файловых систем, но для понимания это всё ещё один длинный ряд страниц.

Страница со слотами

Строки бывают разной длины: имя «Ян» короче имени «Александра». Как уложить строки переменной длины в страницу так, чтобы их можно было находить, удалять и двигать? Почти все реляционные СУБД используют одну и ту же схему, её называют страницей со слотами.

┌───────────────────────────────────────────────┐
│ заголовок │ слот 1 │ слот 2 │ слот 3 │ →       │
│                                               │
│               свободное место                 │
│                                               │
│       ← │ строка 3 │ строка 2 │ строка 1      │
└───────────────────────────────────────────────┘

Устройство такое:

1. В начале страницы лежит заголовок со служебными сведениями.
2. За ним растёт массив слотов. Слот это маленькая запись «строка лежит по такому-то смещению и занимает столько-то байт».
3. Сами строки пишутся с конца страницы навстречу слотам.
4. Между ними остаётся свободное место. Когда слоты и строки встречаются, страница заполнена.

Зачем такая сложность? Адрес строки указывает на слот, а не на байты. Если строку нужно передвинуть внутри страницы, например чтобы собрать свободное место в один кусок, СУБД меняет смещение в слоте, а адрес строки остаётся прежним. Все, кто ссылается на строку по адресу, ничего не замечают.