Своя СУБД на Effect · урок 4: B+Tree индекс
Кому это. К этому уроку у тебя есть три нижних слоя движка на Effect. В уроке 1 появилась страница и DiskManager-сервис, в уроке 2 над диском встал буферный пул на семафоре с withPin, в уроке 3 поверх пула выросла куча: таблица как набор страниц, строка адресуется стабильным RID, sequential scan это Stream. Но у кучи есть одна большая дыра, и сегодня мы её закрываем.
Зачем именно Effect. Найти строку по ключу в куче можно только сканом всей таблицы, O(числа строк). Нужна структура, которая по ключу приводит к RID за считанные обращения к диску и отдаёт ключи по порядку для диапазонных запросов. Это B+Tree. И именно здесь Effect вскрывает грань, которой не было в прошлых уроках: рекурсивный спуск по дереву с вложенными scope. Вставка держит закреплённым весь путь от корня до листа (стек pin-ов), и тут scope рекурсии остаётся открытым на время спуска в ребёнка. А чтение держит один pin за раз, и тут scope закрывается до рекурсивного шага. Форма рекурсии решает, держишь ли ты стек pin-ов или один. Плюс rangeScan это снова Stream, корень дерева живёт в Ref, точечный поиск возвращает Option, а битый файл индекса это BTreeError.
Важно про код. Как и прежде, ты пишешь реализацию с нуля, листинги приведены целиком. Это самый алгоритмически плотный урок воркшопа: расщепление узла с подъёмом разделителя легко понять на картинке и легко напутать в коде на границах. Печатай руками, прогоняй тесты после каждого блока, и обязательно поиграй с виджетом ниже.
Где мы в движке
┌────────────────────────────────────────────────┐
│ Бинарный протокол + TCP-сервер │ урок 11
├────────────────────────────────────────────────┤
│ Исполнитель (Volcano) + EXPLAIN │ урок 6
│ Планировщик, binder, парсер, лексер │ уроки 5, 6
├────────────────────────────────────────────────┤
│ Vacuum │ урок 10
│ MVCC (видимость, снимки) │ уроки 8, 9
│ Блокировки (2PL), менеджер транзакций │ уроки 8, 9
│ WAL (журнал, redo, recovery) │ урок 7
├────────────────────────────────────────────────┤
│ B+Tree индекс │ урок 4 ← мы здесь
│ Куча (slotted pages, seq scan) │ урок 3
├────────────────────────────────────────────────┤
│ Буферный пул (кэш страниц, вытеснение) │ урок 2
│ DiskManager (страницы поверх файла) │ урок 1
└────────────────────────────────────────────────┘Индекс встаёт ровно туда же, куда куча: поверх буферного пула. Узел дерева это страница, и за неё отвечает всё тот же пул из урока 2. Индекс знает только про withPin и withNewPage, на диск напрямую не ходит. Куча отображала RID в строку, индекс отображает ключ в RID. Связка: индекс по ключу находит RID, куча по RID отдаёт строку.
Почему именно B+Tree
На диске единица обмена это не байт и не ключ, а целая страница в 8 КБ. Двоичное дерево хранит по одному ключу в узле, значит на спуске к листу при миллионе ключей оно трогает около 20 узлов, то есть до 20 обращений к диску. Беда не в сравнениях, беда в походах на диск.
B+Tree кладёт в один узел не один ключ, а сотни, сколько влезает в страницу. Это число называется fanout, и именно он делает дерево низким. При fanout в несколько сотен миллионы ключей умещаются в три-четыре уровня, то есть три-четыре прочитанные страницы вместо двадцати.
Буква “плюс” означает конкретное устройство. В B+Tree сами значения (у нас RID) лежат только в листьях. Внутренние узлы хранят лишь разделители. Это даёт два выигрыша. Первый: внутренние узлы не тащат значения, fanout ещё выше. Второй, для нас главный: листья связаны в цепочку слева направо, и диапазонный запрос спускается к первому подходящему листу и дальше бежит по цепочке, не возвращаясь вверх.
И последнее: B+Tree всегда сбалансировано. Все листья на одной глубине, и эта глубина растёт только когда расщепляется корень. Балансировку дерево держит само, через расщепление переполненных узлов снизу вверх. Поиграй: вставляй ключи и смотри, как лист переполняется, делится, как разделитель всплывает наверх и как корень расщепляется.
Если повозился с виджетом, ты видел три вещи, которые сейчас запрограммируешь. Первая: лист переполняется и делится на два, минимальный ключ правого листа копируется наверх как разделитель. Вторая: новые листья встают в цепочку, поэтому скан по порядку идёт слева направо. Третья: высота растёт только при расщеплении корня, и все листья всегда на одном уровне.
Контракт байтов узла
Узел B+Tree это страница, но размечена иначе, чем страница кучи. Куче нужны были слоты, узлу нужен компактный отсортированный массив ячеек. Поэтому узел кладёт заголовок не в начало, а в 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 байт:
смещение размер поле
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 из прошлых уроков константы 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 это тонкий вид на байты страницы как на узел. И снова, как Schema и Tuple, это чистый код без ввода-вывода: читать и писать страницу это дело пула, узел только размечает её содержимое. Поэтому BTreeNode дословно совпадает с TS-треком, без единого Effect. Начнём с каркаса.
// 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-области, а её начало мы только что объявили полем страницы. 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 это бинарный поиск первого ключа, не меньшего искомого. Он вернёт либо позицию точного совпадения, либо место вставки. Поскольку дубликаты разрешены, он находит самый левый из равных, и они оказываются кластером.
leafInsertAt сдвигает хвост вправо через copyWithin, освобождая место под новую ячейку. copyWithin корректно работает на пересекающихся диапазонах, поэтому сдвиг вправо не затирает данные.
leafSplitInto это сердце расщепления листа. Верхняя половина [mid..) копируется в новый правый лист. Дальше критичны две строки про цепочку: сначала правый наследует старого соседа текущего (right.nextLeaf = this.nextLeaf), и только потом текущий указывает на правый (this.nextLeaf = rightPageId). Поменяешь порядок, и 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 лежит отдельно, а ребёнок с индексом i для i >= 1 лежит в ячейке i - 1 рядом со своим разделителем. Этот сдвиг на единицу это самый частый источник ошибок во всём узле.
Два маршрутизатора: route и routeLeftmost. Они отличаются одним знаком сравнения, и это корректность дубликатов. route это upper_bound: при равенстве спуск идёт вправо, туда же вставка кладёт новые равные ключи, значит поиск и вставка ходят одним путём. routeLeftmost это строгий lower_bound: при равенстве уходит влево, к самому левому листу с дубликатом. Им мы начинаем range scan. Поставишь не тот знак, и баг проявится только на дубликатах.
internalSplitInto. В отличие от листа, у внутреннего узла средний разделитель не копируется, а переезжает наверх и не остаётся ни слева, ни справа. Разделитель листа это реальный ключ, который продолжает жить в листе, а разделитель внутреннего узла это чистый указатель-граница, и подняв его наверх, мы делаем его границей на уровень выше.
Размеченная ошибка индекса: BTreeError
У файлового слоя есть IoError, у пула BufferPoolError, у кучи HeapError. У индекса появляются свои сбойные ситуации: открыли файл с битой магией, или validate нашёл нарушение структуры. Добавь в errors.ts ещё один класс.
// src/errors.ts (добавляем рядом с предыдущими)
import { Data } from 'effect';
/**
* Ошибка B+Tree (урок 4). bad-magic: открыли файл, метастраница которого не несёт
* сигнатуру индекса. invariant: validate нашёл нарушение структуры (отладочная проверка).
*/
export class BTreeError extends Data.TaggedError('BTreeError')<{
readonly reason: 'bad-magic' | 'invariant';
readonly message: string;
}> {}Где в TS-треке open бросал Error на битой магии, в порте openBTree вернёт Effect.fail(new BTreeError({ reason: 'bad-magic', ... })). А validate, наша проверка инвариантов для тестов, будет падать BTreeError('invariant') с точным указанием, что и где сломалось.
Главное решение порта: дерево это значение, корень в Ref, два стиля спуска
Как и куча, индекс это значение (таблиц и индексов много), которое мы создаём функцией. createBTree(options) возвращает Effect<BTree, _, BufferPool>: оно достаёт пул из контекста и заводит дерево. Но у дерева есть состояние, которого не было у кучи: корень меняется при расщеплении. В TS это было изменяемое поле rootPageId. В Effect изменяемую ячейку даёт Ref: rootRef: Ref<number> держит page id корня, и writeRoot обновляет и его, и метастраницу на диске.
Но настоящая новая мысль урока в другом: в какой момент рекурсии закрывается scope страницы. От этого зависит, держишь ли ты закреплённым весь путь или одну страницу.
- Чтение (
search,height,descendToLeaf) держит один pin за раз. Спуск устроен так: открыли scope страницы, посчитали номер следующего ребёнка, scope закрылся (pin снят), и только потом рекурсивный шаг идёт в ребёнка. В любой момент закреплён ровно один узел. Это и правильно: читающему спуску не нужен родитель после того, как он выбрал ветку. - Вставка (
insert) держит весь путь закреплённым.insertIntoоборачивает тело вEffect.scopedи делает рекурсивный вызов в ребёнка, пока scope родителя ещё открыт. Вложенные scope образуют стек: на самом дне закреплён весь путь корень, лист, а финалайзеры снимают pin-ы снизу вверх, когда рекурсия разматывается. Это ровно тот стек pin-ов, что в императивной версии набирался естественно через стек вызовов. Вставке родитель нужен после возврата из ребёнка: если ребёнок расщепился, в родителя надо вставить поднятый разделитель.
Запомни этот контраст, он и есть Effect-сторона урока. Форма scoped(...).pipe(flatMap(r => step(r.child))) даёт один pin за раз (scope закрыт до рекурсии). Форма scoped(gen { ... yield* recurse(child) ... }) даёт стек pin-ов (scope открыт сквозь рекурсию). Один и тот же withPin, разный момент закрытия scope, разное поведение по памяти.
дальше после входа
Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.
Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.