Своя СУБД на TS · урок 4: B+Tree индекс
Кому это. К этому уроку у тебя есть три нижних слоя движка. В уроке 1 появилась страница и DiskManager, в уроке 2 над диском встал буферный пул, в уроке 3 поверх пула выросла куча: таблица как набор страниц, строка адресуется стабильным RID, sequential scan обходит всё. Но у кучи есть одна большая дыра, и сегодня мы её закрываем.
Зачем. Найти строку по ключу в куче можно только одним способом: прочитать всю таблицу и сравнить каждую строку. Это O(числа строк), и на миллионе строк один SELECT ... WHERE id = 42 поднимает с диска всю таблицу. Так работать нельзя. Нужна структура, которая по ключу приводит прямо к RID за считанные обращения к диску и при этом умеет отдавать ключи по порядку для диапазонных запросов. Эта структура это B+Tree, рабочая лошадка индексов почти во всех реляционных СУБД.
Важно про код. Как и прежде, ты пишешь реализацию с нуля, листинги приведены целиком и разобраны построчно. Это самый алгоритмически плотный урок воркшопа: расщепление узла с подъёмом разделителя легко понять на картинке и легко напутать в коде на границах. Печатай руками, прогоняй тесты после каждого блока, и обязательно поиграй с виджетом ниже: увидеть split вживую сильно дешевле, чем отлаживать его по логам.
Где мы в движке
┌────────────────────────────────────────────────┐
│ Бинарный протокол + TCP-сервер │ урок 10
├────────────────────────────────────────────────┤
│ Исполнитель (Volcano) + EXPLAIN │ урок 6
│ Планировщик, binder, парсер, лексер │ уроки 5, 6
├────────────────────────────────────────────────┤
│ Vacuum │ урок 9
│ MVCC (видимость, снимки) │ урок 8
│ Блокировки (2PL), менеджер транзакций │ уроки 7, 8
│ WAL (журнал, redo, recovery) │ урок 7
├────────────────────────────────────────────────┤
│ B+Tree индекс │ урок 4 ← мы здесь
│ Куча (slotted pages, seq scan) │ урок 3
├────────────────────────────────────────────────┤
│ Буферный пул (кэш страниц, вытеснение) │ урок 2
│ DiskManager (страницы поверх файла) │ урок 1
└────────────────────────────────────────────────┘Индекс встаёт ровно туда же, куда куча: поверх буферного пула. Узел дерева это страница, и за чтение, запись и аллокацию страниц отвечает всё тот же пул из урока 2. Индекс не знает про диск напрямую, он знает только про fetchPage, unpinPage, newPage. Куча отображала RID в строку, индекс отображает ключ в RID. Связка получается такая: индекс по ключу находит RID, куча по RID отдаёт строку.
Почему именно B+Tree
Прежде чем городить байты, стоит понять, почему индекс это не обычное двоичное дерево поиска, которое ты писал в разделе про алгоритмы.
На диске единица обмена это не байт и не ключ, а целая страница в 8 КБ. Прочитать один байт стоит ровно столько же, сколько прочитать всю страницу: диск так устроен. Двоичное дерево хранит по одному ключу в узле, значит на спуске к листу оно трогает по узлу на каждый бит высоты, и при миллионе ключей это около 20 узлов, то есть до 20 обращений к диску. Беда не в сравнениях, беда в походах на диск.
B+Tree бьёт по этой беде в лоб: он кладёт в один узел не один ключ, а сотни, ровно столько, сколько влезает в страницу. Это число называется fanout, и именно он делает дерево низким. Высота дерева это логарифм числа ключей по основанию fanout. При fanout в несколько сотен миллионы ключей умещаются в три-четыре уровня. Поиск по ключу это спуск от корня к листу, то есть три-четыре прочитанные страницы вместо двадцати. Вот зачем индекс это широкое дерево, а не двоичное.
Буква “плюс” в названии означает конкретное устройство. В B+Tree сами значения (у нас это RID) лежат только в листьях. Внутренние узлы хранят лишь разделители: ключи-указатели, которые говорят, в какую ветку спускаться. Это даёт два выигрыша. Первый: внутренние узлы не тащат значения, поэтому в страницу влезает больше разделителей, fanout ещё выше, дерево ещё ниже. Второй, и для нас главный: листья связаны в цепочку слева направо. Диапазонный запрос (WHERE id BETWEEN 25 AND 60) спускается к первому подходящему листу и дальше просто бежит по цепочке, не возвращаясь вверх. В обычном B-дереве, где значения размазаны по всем уровням, range scan устроен куда мучительнее.
И последнее свойство, которое делает B+Tree деревом, а не просто отсортированным списком страниц: оно всегда сбалансировано. Все листья лежат на одной глубине, и эта глубина растёт только когда расщепляется корень. Балансировку дерево держит само, через расщепление переполненных узлов снизу вверх, без отдельного прохода ребалансировки. Поиграй: вставляй ключи и смотри, как лист переполняется, делится, как разделитель всплывает наверх и как в какой-то момент корень расщепляется и дерево становится выше.
Если повозился с виджетом, ты уже видел три вещи, которые сейчас запрограммируешь. Первая: лист переполняется и делится на два, минимальный ключ правого листа копируется наверх как разделитель. Вторая: новые листья встают в цепочку, поэтому скан по порядку идёт слева направо. Третья: высота растёт только при расщеплении корня, и все листья всегда на одном уровне. Теперь уложим это в байты страниц.
Контракт байтов узла
Узел B+Tree это страница, но размечена она иначе, чем страница кучи. Куча использовала slotted-раскладку: заголовок, массив слотов, данные с конца. Узлу слоты не нужны, ему нужен компактный отсортированный массив ячеек. Поэтому узел переиспользует страницу так: заголовок узла лежит не в начале, а в special-области в конце страницы, а ячейки пакуются подряд от начала области данных вверх к этому заголовку. Числа little-endian, как и весь дисковый формат (см. контракт).
Заголовок узла это 8 байт, он начинается со смещения special = PAGE_SIZE - 8:
смещение размер поле
0 2 node_type u16 0 = internal, 1 = leaf
2 2 key_count u16 число разделителей (внутр.) или ячеек (лист)
4 4 next_leaf u32 page id следующего листа (0 = нет); только у листьевЛист хранит отсортированные по ключу ячейки (key, rid) фиксированной длины 14 байт. Ключ это знаковый int (тот же тип, что в куче), RID это пара (page id кучи, слот):
смещение размер поле
0 8 key i64 ключ (знаковый)
8 4 rid_page u32 page id кучи
12 2 rid_slot u16 слот кучиЛистья связаны через next_leaf в цепочку по возрастанию ключей: это и есть тот рельс, по которому катится range scan.
Внутренний узел устроен чуть хитрее. Детей у него на один больше, чем разделителей, потому что разделитель стоит между двумя ветками. Поэтому первый, самый левый ребёнок (назовём его child0) хранится отдельным ведущим указателем, а дальше идут ячейки (separator, child):
смещение размер поле
16 4 child0 u32 самый левый ребёнок
20 + i*12 8 separator i64 разделитель s_i
20 + i*12 + 8 4 child u32 ребёнок c_(i+1)Разделитель s_i это минимальный ключ поддерева child(i+1), а child0 держит ключи меньше s_0. Спуск по ключу K это число разделителей, у которых s_i <= K: равенство уходит вправо, ровно туда, куда вставка кладёт новые равные ключи. Дубликаты ключей разрешены, поэтому начало range scan спускается по самому левому ребёнку с s_i >= K, чтобы не проскочить дубликаты в листьях левее.
Наконец, файл индекса самоописывающий. Page 0 это метастраница, которая держит указатель на корень, остальные страницы это узлы. Корень переживает перезапуск именно через метастраницу:
смещение размер поле
0 4 magic u32 0x42545231 ("BTR1")
4 4 root u32 page id корня (переживает перезапуск)Корнем при создании индекса становится лист (page 1). Когда корень расщепляется, заводится новый внутренний корень, и его page id переписывается в метастраницу.
Константы узла
Добавь к constants.ts из прошлых уроков (там уже лежат PAGE_SIZE, HEADER_SIZE, SLOT_SIZE и смещения заголовков страницы и кортежа) константы B+Tree.
// src/constants.ts (добавляем к написанному в уроках 1 и 3)
/** Размер заголовка узла: nodeType u16, keyCount u16, nextLeaf u32. */
export const NODE_HEADER_SIZE = 8;
/** Начало special-области узла (туда кладётся заголовок узла). */
export const BTREE_SPECIAL = PAGE_SIZE - NODE_HEADER_SIZE;
/** Тип узла (хранится в заголовке узла). */
export const NodeType = {
internal: 0,
leaf: 1,
} as const;
/** Смещения полей заголовка узла внутри special-области. */
export const NodeHeaderOffset = {
nodeType: 0,
keyCount: 2,
nextLeaf: 4,
} as const;
/** Ячейка листа: key i64 (8) + rid.pageId u32 (4) + rid.slot u16 (2). */
export const LEAF_CELL_SIZE = 14;
/** Смещение ведущего указателя child0 во внутреннем узле (сразу за заголовком страницы). */
export const INTERNAL_CHILD0_OFFSET = HEADER_SIZE;
/** Ячейка внутреннего узла: separator i64 (8) + child u32 (4). */
export const INTERNAL_CELL_SIZE = 12;
/** Сентинел "нет соседнего листа" в nextLeaf. Page 0 это метастраница, не лист. */
export const NO_SIBLING = 0;
/** Магия метастраницы индекса (page 0): ASCII "BTR1". */
export const BTREE_META_MAGIC = 0x42_54_52_31;
/** Смещения полей метастраницы индекса. */
export const MetaOffset = {
magic: 0,
root: 4,
} as const;Заметь два сентинела. NO_SIBLING это 0, и это безопасно: следующим листом не может быть page 0, потому что page 0 это метастраница, а не узел. BTREE_META_MAGIC это четыре ASCII-байта BTR1: при открытии индекса мы сверим магию и упадём с понятной ошибкой, если открыли не тот файл, а не прочитаем мусор как номер корня.
BTreeNode: вид на страницу как на узел
Как Tuple в уроке 3 был тонким видом на байты кортежа, так BTreeNode это тонкий типизированный вид на байты страницы как на узел дерева. Без всякого ввода-вывода: читать и писать страницу на диск это дело пула, узел только размечает её содержимое. Начнём с каркаса и инициализации.
// src/btree-node.ts
import {
BTREE_SPECIAL,
HEADER_SIZE,
INTERNAL_CELL_SIZE,
INTERNAL_CHILD0_OFFSET,
LEAF_CELL_SIZE,
NO_SIBLING,
NodeHeaderOffset,
NodeType,
} from '~/constants.ts';
import type { Rid } from '~/heap-file.ts';
import type { Page } from '~/page.ts';
/** Смещение поля rid.pageId внутри ячейки листа. */
const LEAF_PAGE_ID_OFFSET = 8;
/** Смещение поля rid.slot внутри ячейки листа. */
const LEAF_SLOT_OFFSET = 12;
/** Смещение поля child внутри ячейки внутреннего узла. */
const INTERNAL_CHILD_OFFSET = 8;
export class BTreeNode {
readonly page: Page;
private readonly buffer: Buffer;
constructor(page: Page) {
this.page = page;
this.buffer = page.buffer;
}
/** Инициализировать страницу как пустой лист. Сначала выставляем special. */
static initLeaf(page: Page): BTreeNode {
page.special = BTREE_SPECIAL;
const node = new BTreeNode(page);
node.writeNodeType(NodeType.leaf);
node.keyCount = 0;
node.nextLeaf = NO_SIBLING;
return node;
}
/** Инициализировать страницу как пустой внутренний узел. */
static initInternal(page: Page): BTreeNode {
page.special = BTREE_SPECIAL;
const node = new BTreeNode(page);
node.writeNodeType(NodeType.internal);
node.keyCount = 0;
node.nextLeaf = NO_SIBLING;
return node;
}
get isLeaf(): boolean {
return this.buffer.readUInt16LE(BTREE_SPECIAL + NodeHeaderOffset.nodeType) === NodeType.leaf;
}
get keyCount(): number {
return this.buffer.readUInt16LE(BTREE_SPECIAL + NodeHeaderOffset.keyCount);
}
set keyCount(value: number) {
this.buffer.writeUInt16LE(value, BTREE_SPECIAL + NodeHeaderOffset.keyCount);
}
get nextLeaf(): number {
return this.buffer.readUInt32LE(BTREE_SPECIAL + NodeHeaderOffset.nextLeaf);
}
set nextLeaf(value: number) {
this.buffer.writeUInt32LE(value, BTREE_SPECIAL + NodeHeaderOffset.nextLeaf);
}
// методы листа и внутреннего узла ниже
private writeNodeType(type: number): void {
this.buffer.writeUInt16LE(type, BTREE_SPECIAL + NodeHeaderOffset.nodeType);
}
private leafCellOffset(index: number): number {
return HEADER_SIZE + index * LEAF_CELL_SIZE;
}
private internalCellOffset(index: number): number {
return INTERNAL_CHILD0_OFFSET + 4 + index * INTERNAL_CELL_SIZE;
}
}Обрати внимание на порядок в initLeaf: сначала page.special = BTREE_SPECIAL, потом всё остальное. Заголовок узла лежит в special-области, а её начало мы только что объявили полем страницы. keyCount и nextLeaf это просто аксессоры к двум полям в special, а leafCellOffset/internalCellOffset считают, где лежит ячейка с данным индексом: ячейки идут подряд от HEADER_SIZE (для внутреннего узла после ведущего child0, поэтому плюс 4). Дальше всё ветвление будет про две раскладки: лист и внутренний узел.
Методы листа
Лист это отсортированный массив ячеек (key, rid). Чтение ячейки, бинарный поиск по ключу, вставка со сдвигом хвоста и расщепление.
// -------- лист --------
/** Ключ ячейки листа по индексу. */
keyAt(index: number): bigint {
return this.buffer.readBigInt64LE(this.leafCellOffset(index));
}
/** RID ячейки листа по индексу. */
ridAt(index: number): Rid {
const offset = this.leafCellOffset(index);
return {
pageId: this.buffer.readUInt32LE(offset + LEAF_PAGE_ID_OFFSET),
slot: this.buffer.readUInt16LE(offset + LEAF_SLOT_OFFSET),
};
}
/** Первый индекс, где keyAt(index) >= key (lower_bound). Дубликаты кластеризуются. */
lowerBound(key: bigint): number {
let low = 0;
let high = this.keyCount;
while (low < high) {
const middle = (low + high) >>> 1;
if (this.keyAt(middle) < key) {
low = middle + 1;
} else {
high = middle;
}
}
return low;
}
/** Вставить ячейку листа в позицию index, сдвинув хвост вправо. */
leafInsertAt(index: number, key: bigint, rid: Rid): void {
const count = this.keyCount;
const target = this.leafCellOffset(index);
if (index < count) {
this.buffer.copyWithin(this.leafCellOffset(index + 1), target, this.leafCellOffset(count));
}
this.buffer.writeBigInt64LE(key, target);
this.buffer.writeUInt32LE(rid.pageId, target + LEAF_PAGE_ID_OFFSET);
this.buffer.writeUInt16LE(rid.slot, target + LEAF_SLOT_OFFSET);
this.keyCount = count + 1;
}
/**
* Разрезать лист: ячейки [mid..) переезжают в right, в текущем остаётся [0..mid).
* Связь листьев: right.nextLeaf = старый this.nextLeaf, затем this.nextLeaf =
* rightPageId. Порядок важен, иначе порвём цепочку для range scan.
*/
leafSplitInto(right: BTreeNode, rightPageId: number, mid: number): void {
const count = this.keyCount;
this.buffer.copy(
right.buffer,
HEADER_SIZE,
this.leafCellOffset(mid),
this.leafCellOffset(count),
);
right.keyCount = count - mid;
right.nextLeaf = this.nextLeaf;
this.keyCount = mid;
this.nextLeaf = rightPageId;
}Разберём ключевое.
lowerBound это бинарный поиск первого ключа, не меньшего искомого. Он вернёт либо позицию точного совпадения, либо место, куда ключ надо вставить, чтобы массив остался отсортированным. На этом стоит и точечный поиск (там после lowerBound мы сверяем, что ключ действительно равен искомому), и вставка (туда мы и вставляем). Поскольку дубликаты разрешены, lowerBound находит самый левый из равных, и они оказываются рядом, кластером.
leafInsertAt сдвигает хвост вправо через copyWithin, освобождая место под новую ячейку, и пишет её. copyWithin это копирование в пределах одного буфера, оно корректно работает на пересекающихся диапазонах, поэтому сдвиг вправо не затирает данные. Если вставляем в конец (index === count), сдвигать нечего.
leafSplitInto это сердце расщепления листа. Верхняя половина ячеек [mid..) копируется в новый правый лист, в текущем остаётся нижняя [0..mid). Дальше критичные две строки про цепочку: сначала правый лист наследует старого соседа текущего (right.nextLeaf = this.nextLeaf), и только потом текущий начинает указывать на правый (this.nextLeaf = rightPageId). Поменяешь порядок, и right укажет сам на себя или потеряет хвост цепочки, и range scan либо зациклится, либо оборвётся. Порядок тут не стилистика, а корректность.
Методы внутреннего узла
Внутренний узел это ведущий child0 плюс массив ячеек (separator, child). Чтение детей и разделителей, два варианта маршрутизации, вставка разделителя и расщепление.
// -------- внутренний узел --------
/** Дочерний указатель по индексу. child0 это ведущий указатель, остальные в ячейках. */
childAt(index: number): number {
if (index === 0) {
return this.buffer.readUInt32LE(INTERNAL_CHILD0_OFFSET);
}
return this.buffer.readUInt32LE(this.internalCellOffset(index - 1) + INTERNAL_CHILD_OFFSET);
}
setChildAt(index: number, child: number): void {
if (index === 0) {
this.buffer.writeUInt32LE(child, INTERNAL_CHILD0_OFFSET);
return;
}
this.buffer.writeUInt32LE(child, this.internalCellOffset(index - 1) + INTERNAL_CHILD_OFFSET);
}
/** Разделитель по индексу: минимальный ключ поддерева childAt(index + 1). */
separatorAt(index: number): bigint {
return this.buffer.readBigInt64LE(this.internalCellOffset(index));
}
/**
* Индекс ребёнка для спуска по ключу: число разделителей с s <= key (upper_bound).
* Равенство уходит вправо, ровно куда вставка кладёт новые равные ключи. Это путь
* для insert и точечного search.
*/
route(key: bigint): number {
let low = 0;
let high = this.keyCount;
while (low < high) {
const middle = (low + high) >>> 1;
if (this.separatorAt(middle) <= key) {
low = middle + 1;
} else {
high = middle;
}
}
return low;
}
/**
* Индекс самого левого ребёнка, который может содержать key: число разделителей с
* s < key (lower_bound, строго). Равенство уходит влево. Это путь для начала range
* scan, чтобы не пропустить дубликаты в листьях левее.
*/
routeLeftmost(key: bigint): number {
let low = 0;
let high = this.keyCount;
while (low < high) {
const middle = (low + high) >>> 1;
if (this.separatorAt(middle) < key) {
low = middle + 1;
} else {
high = middle;
}
}
return low;
}
/** Вставить разделитель в позицию index, новый правый ребёнок встаёт на index + 1. */
internalInsertAt(index: number, separator: bigint, child: number): void {
const count = this.keyCount;
const target = this.internalCellOffset(index);
if (index < count) {
this.buffer.copyWithin(
this.internalCellOffset(index + 1),
target,
this.internalCellOffset(count),
);
}
this.buffer.writeBigInt64LE(separator, target);
this.buffer.writeUInt32LE(child, target + INTERNAL_CHILD_OFFSET);
this.keyCount = count + 1;
}
/**
* Разрезать внутренний узел: средний разделитель s[mid] поднимается наверх (НЕ
* остаётся), left держит s[0..mid) и c[0..mid], right получает c[mid+1] как child0
* плюс s[mid+1..) и c[mid+2..). Возвращает поднимаемый разделитель.
*/
internalSplitInto(right: BTreeNode, mid: number): bigint {
const count = this.keyCount;
const promoted = this.separatorAt(mid);
right.setChildAt(0, this.childAt(mid + 1));
let rightIndex = 0;
for (let source = mid + 1; source < count; source++) {
right.writeSeparatorAt(rightIndex, this.separatorAt(source));
right.setChildAt(rightIndex + 1, this.childAt(source + 1));
rightIndex++;
}
right.keyCount = count - mid - 1;
this.keyCount = mid;
return promoted;
}
private writeSeparatorAt(index: number, separator: bigint): void {
this.buffer.writeBigInt64LE(separator, this.internalCellOffset(index));
}Здесь два момента, в которых легко запутаться, поэтому разберём подробно.
childAt и сдвиг на один. Детей на один больше, чем разделителей. Ведущий child0 лежит отдельно (по INTERNAL_CHILD0_OFFSET), а ребёнок с индексом i для i >= 1 лежит в ячейке i - 1 рядом со своим разделителем. Поэтому childAt(0) читает ведущий указатель, а childAt(i) для остальных лезет в ячейку. Этот сдвиг на единицу между нумерацией детей и нумерацией разделителей это самый частый источник ошибок во всём узле, держи его в голове.
Два маршрутизатора: route и routeLeftmost. Они отличаются одним знаком сравнения, и это не придирка, а корректность дубликатов. route это upper_bound: разделители с s <= key уводят вправо, поэтому при равенстве ключа разделителю спуск идёт в правую ветку. Туда же вставка кладёт новые равные ключи, значит поиск и вставка ходят одним путём. routeLeftmost это строгий lower_bound: при равенстве он уходит влево, к самому левому листу, где может лежать дубликат искомого ключа. Им мы начинаем range scan, чтобы не проскочить равные ключи, осевшие в листе левее. Поставишь не тот знак, и точечный поиск дубля иногда промахнётся, а range scan потеряет первые совпадения. Это тот самый баг, который проявляется только на дубликатах и которого нет в простых тестах.
internalSplitInto. В отличие от листа, у внутреннего узла средний разделитель не копируется, а переезжает наверх и не остаётся ни в левом, ни в правом. Это и логично: разделитель листа это реальный ключ, который продолжает жить в листе, а разделитель внутреннего узла это чистый указатель-граница, и подняв его наверх, мы как раз делаем его границей между левой и правой половинами на уровень выше. Правый узел получает child(mid+1) ведущим, дальше разделители и детей после mid.
дальше после входа
Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.
Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.