Своя СУБД на Go · урок 4: B+Tree индекс
Кому это. К этому уроку у тебя есть три нижних слоя движка на Go. В уроке 1 появилась страница page.Page как массив [8192]byte и disk.Manager поверх *os.File. В уроке 2 над диском встал буферный пул под sync.Mutex с парой FetchPage и UnpinPage. В уроке 3 поверх пула выросла куча: таблица как набор страниц, строка адресуется стабильным heap.Rid, seq scan это курсор с методом Next. Но у кучи есть одна большая дыра, и сегодня мы её закрываем.
Зачем именно Go. Найти строку по ключу в куче можно только сканом всей таблицы, O(числа строк). Нужна структура, которая по ключу приводит к RID за считанные обращения к диску и отдаёт ключи по порядку для диапазонных запросов. Это B+Tree. И здесь Go показывает две вещи, которых в прошлых уроках было мало. Первая: замыкания как способ передать поведение. Спуск по дереву один, а куда сворачивать на каждом узле, решает переданная функция route func(Node) int. Вторая: defer как гарантия снятия pin. Каждое закрепление страницы в дереве снимается в defer, поэтому ни одна ветка с ранним return err не оставит кадр пула занятым. А форма кода решает, держишь ли ты закреплённым один узел (цикл спуска) или весь путь от корня до листа (рекурсия вставки).
Важно про код. Как и прежде, ты пишешь реализацию с нуля, в своём модуле ourdb на Go 1.23, только стандартная библиотека. Листинги взяты из эталона examples/our-db/go, там, где я что-то сократил, это сказано прямо. Это самый алгоритмически плотный урок воркшопа: расщепление узла с подъёмом разделителя легко понять на картинке и легко напутать в коде на границах. Печатай руками, гоняй go test ./btree/ после каждого блока и обязательно поиграй с виджетом ниже.
Где мы в движке
┌────────────────────────────────────────────────┐
│ Бинарный протокол + 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
└────────────────────────────────────────────────┘Индекс встаёт туда же, куда куча: поверх буферного пула. Узел дерева это страница, и за неё отвечает всё тот же *bufferpool.Pool из урока 2. Пакет btree знает только про FetchPage, NewPage и UnpinPage, на диск напрямую не ходит. Куча отображала RID в строку, индекс отображает ключ в RID. Связка такая: индекс по ключу находит RID, куча по RID отдаёт строку.
В раскладке модуля это новый пакет рядом с прошлыми:
ourdb/
├── go.mod module ourdb, go 1.23
├── page/ урок 1
├── disk/ урок 1
├── bufferpool/ урок 2
├── tuple/ урок 3
├── heap/ урок 3
└── btree/ урок 4 ← node.go, btree.go, validate.go, delete.gobtree импортирует page, bufferpool и heap (ему нужен тип heap.Rid). Обратных импортов нет: куча не знает, что над ней построят индекс. Go это проверяет за тебя, цикл импорта не скомпилируется.
Почему именно B+Tree
На диске единица обмена это не байт и не ключ, а целая страница в 8 КБ. Двоичное дерево хранит по одному ключу в узле, значит на спуске к листу при миллионе ключей оно трогает около 20 узлов, то есть до 20 обращений к диску. Беда не в сравнениях, беда в походах на диск.
B+Tree кладёт в один узел не один ключ, а сотни, сколько влезает в страницу. Это число называется fanout, и именно он делает дерево низким. При fanout в несколько сотен миллионы ключей умещаются в три-четыре уровня, то есть три-четыре прочитанные страницы вместо двадцати.
Буква “плюс” означает конкретное устройство. В B+Tree сами значения (у нас RID) лежат только в листьях. Внутренние узлы хранят лишь разделители. Это даёт два выигрыша. Первый: внутренние узлы не тащат значения, fanout ещё выше. Второй, для нас главный: листья связаны в цепочку слева направо, и диапазонный запрос спускается к первому подходящему листу и дальше бежит по цепочке, не возвращаясь вверх.
И последнее: B+Tree всегда сбалансировано. Все листья на одной глубине, и эта глубина растёт только когда расщепляется корень. Баланс дерево держит само, через расщепление переполненных узлов снизу вверх. Поиграй: вставляй ключи и смотри, как лист переполняется, делится, как разделитель всплывает наверх и как корень расщепляется.
Если повозился с виджетом, ты видел три вещи, которые сейчас запрограммируешь. Первая: лист переполняется и делится на два, минимальный ключ правого листа копируется наверх как разделитель. Вторая: новые листья встают в цепочку, поэтому скан по порядку идёт слева направо. Третья: высота растёт только при расщеплении корня, и все листья всегда на одном уровне.
Контракт байтов узла
Узел B+Tree это страница, но размечена иначе, чем страница кучи. Куче нужны были слоты, узлу нужен компактный отсортированный массив ячеек. Поэтому узел кладёт заголовок не в начало, а в special-область в конце страницы, а ячейки пакует подряд от начала области данных вверх. Числа little-endian, как весь дисковый формат: файл индекса, записанный Go-портом, читается TS-эталоном и наоборот.
Заголовок узла это 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 спускается по самому левому ребёнку, который может держать K, чтобы не проскочить дубликаты в листьях левее.
Наконец, файл индекса самоописывающий. Page 0 это метастраница с указателем на корень, остальные страницы это узлы:
смещение размер поле
0 4 magic u32 0x42545231 ("BTR1")
4 4 root u32 page id корня (переживает перезапуск)Корнем при создании становится лист (page 1). Когда корень расщепляется, заводится новый внутренний корень, и его page id переписывается в метастраницу.
Константы узла
Заводи пакет btree и файл node.go. Начинается он с констант раскладки, все смещения из таблиц выше.
// btree/node.go
package btree
import (
"encoding/binary"
"ourdb/heap"
"ourdb/page"
)
// Раскладка узла (SPEC.md, раздел "Узел B+Tree"): заголовок узла в special-области в конце
// страницы, ячейки пакуются от page.HeaderSize вверх. Slotted lower/upper не используются.
const (
// NodeHeaderSize это nodeType u16, keyCount u16, nextLeaf u32.
NodeHeaderSize = 8
// Special это начало special-области узла.
Special = page.Size - NodeHeaderSize
// LeafCellSize это key i64 + rid.pageId u32 + rid.slot u16.
LeafCellSize = 14
// InternalCellSize это separator i64 + child u32.
InternalCellSize = 12
// NoSibling это "нет соседнего листа": page 0 это метастраница, не лист.
NoSibling = 0
// MetaMagic это магия метастраницы индекса: ASCII "BTR1".
MetaMagic = 0x42545231
TypeInternal = 0
TypeLeaf = 1
child0Offset = page.HeaderSize
cellsOffset = child0Offset + 4
)
var le = binary.LittleEndianЗдесь три детали, на которых держится остальной файл.
Константы без типа. Special = page.Size - NodeHeaderSize считается при компиляции и остаётся нетипизированной константой: в выражении n.P[Special+2:] она станет int. Так же TypeLeaf в сравнении le.Uint16(n.P[Special:]) == TypeLeaf станет uint16, и никаких приведений вокруг. А константное смещение за пределами страницы поймает компилятор, а не тест: n.P[Special+10:] для массива [8192]byte не соберётся с ошибкой index 8194 out of bounds.
Два сентинела. NoSibling это 0, и это безопасно: следующим листом не может быть page 0, потому что page 0 это метастраница. MetaMagic это четыре ASCII-байта BTR1: при открытии индекса мы сверим магию и вернём понятную ошибку, если открыли не тот файл.
Строчные имена. child0Offset и cellsOffset начинаются со строчной буквы, значит снаружи пакета их не видно. Экспортированы только константы контракта, на которые опираются тесты (Special, TypeLeaf, LeafCellSize). Это та же граница видимости, что ты видел в уроке про структуры и методы: регистр первой буквы и есть модификатор доступа.
Node: вид на страницу как на узел
Как tuple.Deserialize в уроке 3 читал кортеж прямо из байтов страницы, так Node это тонкий вид на байты страницы как на узел. Ввода-вывода в нём нет: поднять страницу из пула это дело дерева, узел только размечает её содержимое.
// Node это типизированный вид над страницей как над узлом B+Tree, без ввода-вывода.
type Node struct {
P *page.Page
}
// InitLeaf размечает страницу как пустой лист.
func InitLeaf(p *page.Page) Node { return initNode(p, TypeLeaf) }
// InitInternal размечает страницу как пустой внутренний узел.
func InitInternal(p *page.Page) Node { return initNode(p, TypeInternal) }
func initNode(p *page.Page, typ uint16) Node {
p.SetSpecial(Special)
le.PutUint16(p[Special:], typ)
n := Node{p}
n.SetKeyCount(0)
n.SetNextLeaf(NoSibling)
return n
}
func (n Node) IsLeaf() bool { return le.Uint16(n.P[Special:]) == TypeLeaf }
func (n Node) KeyCount() int { return int(le.Uint16(n.P[Special+2:])) }
func (n Node) SetKeyCount(c int) { le.PutUint16(n.P[Special+2:], uint16(c)) }
func (n Node) NextLeaf() uint32 { return le.Uint32(n.P[Special+4:]) }
func (n Node) SetNextLeaf(v uint32) { le.PutUint32(n.P[Special+4:], v) }Присмотрись к получателю методов. SetKeyCount меняет данные, а получатель у него n Node, по значению, не *Node. Почему запись не теряется?
Потому что копируется не страница, а структура из одного поля, указателя. Node{p} весит восемь байт, и копия n внутри метода указывает на ту же страницу в кадре пула, что и оригинал. le.PutUint16(n.P[Special+2:], ...) пишет в эти общие байты. Получатель по указателю здесь не нужен: менять в самой Node нечего, у неё нет своего состояния, только адрес чужого. Если механика “копия значения, внутри которого указатель” кажется скользкой, вернись к уроку про значимые и ссылочные типы и к уроку про указатели: это ровно тот случай.
Отсюда же дешевизна. Узлов за один спуск создаётся столько, сколько уровней в дереве, и каждый это значение на стеке, без выделения в куче. Обёртка вида ничего не стоит.
И порядок в initNode: сначала p.SetSpecial(Special), потом всё остальное. Заголовок узла лежит в special-области, и её начало мы объявляем полем заголовка страницы из урока 1. Тот же метод SetSpecial раньше ставил page.Size для кучи.
Методы листа
Лист это отсортированный массив ячеек (key, rid). Чтение ячейки, бинарный поиск по ключу, вставка со сдвигом хвоста, удаление и расщепление.
// -------- лист --------
func leafCell(i int) int { return page.HeaderSize + i*LeafCellSize }
// KeyAt это ключ ячейки листа.
func (n Node) KeyAt(i int) int64 { return int64(le.Uint64(n.P[leafCell(i):])) }
// RidAt это RID ячейки листа.
func (n Node) RidAt(i int) heap.Rid {
off := leafCell(i)
return heap.Rid{PageID: le.Uint32(n.P[off+8:]), Slot: le.Uint16(n.P[off+12:])}
}
// LowerBound это первый индекс с KeyAt >= key. Дубликаты кластеризуются.
func (n Node) LowerBound(key int64) int {
lo, hi := 0, n.KeyCount()
for lo < hi {
mid := (lo + hi) / 2
if n.KeyAt(mid) < key {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
// LeafInsertAt вставляет ячейку в позицию i, сдвигая хвост вправо.
func (n Node) LeafInsertAt(i int, key int64, rid heap.Rid) {
count := n.KeyCount()
at := leafCell(i)
copy(n.P[leafCell(i+1):], n.P[at:leafCell(count)])
le.PutUint64(n.P[at:], uint64(key))
le.PutUint32(n.P[at+8:], rid.PageID)
le.PutUint16(n.P[at+12:], rid.Slot)
n.SetKeyCount(count + 1)
}
// LeafDeleteAt удаляет ячейку i, сдвигая хвост влево.
func (n Node) LeafDeleteAt(i int) {
count := n.KeyCount()
copy(n.P[leafCell(i):], n.P[leafCell(i+1):leafCell(count)])
n.SetKeyCount(count - 1)
}
// LeafSplitInto переносит ячейки [mid..) в right. Порядок связи важен: right.next = старый
// this.next, затем this.next = right, иначе цепочка листьев для range scan порвётся.
func (n Node) LeafSplitInto(right Node, rightID uint32, mid int) {
count := n.KeyCount()
copy(right.P[page.HeaderSize:], n.P[leafCell(mid):leafCell(count)])
right.SetKeyCount(count - mid)
right.SetNextLeaf(n.NextLeaf())
n.SetKeyCount(mid)
n.SetNextLeaf(rightID)
}KeyAt и знак ключа. binary.LittleEndian умеет только беззнаковые числа: Uint64 и PutUint64. Знаковый ключ превращается в байты через uint64(key) и обратно через int64(...). В Go такое приведение между целыми одной ширины не трогает биты, меняется только их толкование, поэтому -1 ляжет как восемь байт 0xff и вернётся как -1. Именно поэтому в тестах есть отдельный случай с отрицательным ключом: если где-то по дороге потеряется знак, сортировка поедет.
RidAt возвращает heap.Rid по значению. Это структура из uint32 и uint16, её можно сравнивать оператором ==. Тесты так и пишут: n.RidAt(0) != (heap.Rid{PageID: 3, Slot: 5}). Никакого Equal, никакого reflect.
LowerBound это бинарный поиск первого ключа, не меньшего искомого. Он вернёт либо позицию точного совпадения, либо место вставки. Дубликаты разрешены, поэтому он находит самый левый из равных, и они оказываются кластером.
LeafInsertAt и встроенный copy. Сдвиг хвоста вправо на одну ячейку это одна строка: copy(dst, src), где оба среза смотрят в одну и ту же страницу и перекрываются. Спецификация Go прямо разрешает перекрытие: copy работает как memmove, а не как побайтовый цикл слева направо, поэтому данные не затираются. Заметь, что проверки if i < count нет. При вставке в конец n.P[at:leafCell(count)] пустой, и copy пустого среза ничего не делает. Граничный случай закрыт семантикой самого языка.
LeafSplitInto это сердце расщепления листа. Верхняя половина [mid..) копируется в новый правый лист, снова одним copy, но уже между двумя разными страницами. Дальше критичны две строки про цепочку: сначала правый наследует старого соседа текущего (right.SetNextLeaf(n.NextLeaf())), и только потом текущий указывает на правый (n.SetNextLeaf(rightID)). Поменяешь порядок, и range scan либо зациклится, либо оборвётся.
Методы внутреннего узла
Внутренний узел это ведущий child0 плюс массив ячеек (separator, child). В листинге только то, что нужно поиску и вставке; методы для удаления (FindLeaf, InternalPrependChild, InternalDeleteAt, InternalRemoveFirst, InternalRemoveLast) живут в том же файле эталона и разобраны в упражнении про удаление.
// -------- внутренний узел (сокращено: без методов удаления) --------
func internalCell(i int) int { return cellsOffset + i*InternalCellSize }
// ChildAt это дочерний указатель: child0 ведущий, остальные в ячейках.
func (n Node) ChildAt(i int) uint32 {
if i == 0 {
return le.Uint32(n.P[child0Offset:])
}
return le.Uint32(n.P[internalCell(i-1)+8:])
}
// SetChildAt пишет дочерний указатель.
func (n Node) SetChildAt(i int, child uint32) {
if i == 0 {
le.PutUint32(n.P[child0Offset:], child)
return
}
le.PutUint32(n.P[internalCell(i-1)+8:], child)
}
// SeparatorAt это минимальный ключ поддерева ChildAt(i + 1).
func (n Node) SeparatorAt(i int) int64 { return int64(le.Uint64(n.P[internalCell(i):])) }
// SetSeparatorAt перезаписывает разделитель (при borrow).
func (n Node) SetSeparatorAt(i int, sep int64) { le.PutUint64(n.P[internalCell(i):], uint64(sep)) }
// Route это индекс ребёнка для спуска по ключу: число разделителей с s <= key. Равенство
// уходит вправо, куда вставка кладёт новые равные ключи.
func (n Node) Route(key int64) int { return n.countSeparators(func(s int64) bool { return s <= key }) }
// RouteLeftmost это число разделителей с s < key: самый левый ребёнок, который может держать
// key. Начало range scan, чтобы не пропустить дубликаты в листьях левее.
func (n Node) RouteLeftmost(key int64) int {
return n.countSeparators(func(s int64) bool { return s < key })
}
func (n Node) countSeparators(below func(int64) bool) int {
lo, hi := 0, n.KeyCount()
for lo < hi {
mid := (lo + hi) / 2
if below(n.SeparatorAt(mid)) {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
// InternalInsertAt вставляет разделитель в позицию i, новый правый ребёнок встаёт на i + 1.
func (n Node) InternalInsertAt(i int, sep int64, child uint32) {
count := n.KeyCount()
at := internalCell(i)
copy(n.P[internalCell(i+1):], n.P[at:internalCell(count)])
le.PutUint64(n.P[at:], uint64(sep))
le.PutUint32(n.P[at+8:], child)
n.SetKeyCount(count + 1)
}
// InternalAppend дописывает (separator, child) в конец.
func (n Node) InternalAppend(sep int64, child uint32) { n.InternalInsertAt(n.KeyCount(), sep, child) }
// InternalSplitInto режет узел: s[mid] поднимается наверх и не остаётся ни в одном узле,
// left держит s[0..mid) и c[0..mid], right получает c[mid+1] как child0 и хвост.
func (n Node) InternalSplitInto(right Node, mid int) int64 {
count := n.KeyCount()
promoted := n.SeparatorAt(mid)
right.SetChildAt(0, n.ChildAt(mid+1))
for src, dst := mid+1, 0; src < count; src, dst = src+1, dst+1 {
right.SetSeparatorAt(dst, n.SeparatorAt(src))
right.SetChildAt(dst+1, n.ChildAt(src+1))
}
right.SetKeyCount(count - mid - 1)
n.SetKeyCount(mid)
return promoted
}Три момента, в которых легко запутаться.
ChildAt и сдвиг на один. Детей на один больше, чем разделителей. Ведущий child0 лежит отдельно, а ребёнок с индексом i для i >= 1 лежит в ячейке i - 1 рядом со своим разделителем. Этот сдвиг на единицу самый частый источник ошибок во всём узле.
Два маршрута, один бинарный поиск. Route и RouteLeftmost отличаются одним знаком сравнения, и от этого знака зависит корректность дубликатов. Route это upper bound: при равенстве спуск идёт вправо, туда же вставка кладёт новые равные ключи, значит поиск и вставка ходят одним путём. RouteLeftmost это строгий lower bound: при равенстве уходит влево, к самому левому листу с дубликатом, им мы начинаем range scan. В TS-эталоне это две копии бинарного поиска. В Go бинарный поиск написан один раз, в countSeparators, а отличие передаётся аргументом: функцией below func(int64) bool. Литерал func(s int64) bool { return s <= key } это замыкание: он помнит key из Route, хотя countSeparators о ключе ничего не знает и зовёт его как below(s). Если этот приём ещё не вошёл в руки, загляни в урок про функции и замыкания. Дальше в уроке он будет встречаться на каждом шагу.
InternalSplitInto. В отличие от листа, у внутреннего узла средний разделитель не копируется, а переезжает наверх и не остаётся ни слева, ни справа. Разделитель листа это реальный ключ, который продолжает жить в листе. Разделитель внутреннего узла это только граница, и подняв его наверх, мы делаем его границей уровнем выше. Цикл переноса хвоста ведёт два индекса сразу: for src, dst := mid+1, 0; ...; src, dst = src+1, dst+1. Множественное присваивание в заголовке for избавляет от второго счётчика снаружи цикла.
Почему здесь не copy, как у листа? У правого узла меняется роль первого ребёнка: c[mid+1] становится его child0, ведущим указателем по смещению 16, а не ячейкой. Хвост ячеек можно было бы перенести одним copy, а child0 записать отдельно, но тогда пришлось бы держать в голове смещения ячеек с обеих сторон. Цикл через SeparatorAt и SetChildAt повторяет определение из контракта дословно, и ошибиться в нём труднее.
Ошибки индекса: обычные значения error
У файлового слоя ошибка это то, что вернул *os.File, у пула есть сторожевая bufferpool.ErrExhausted, у кучи fmt.Errorf с описанием. У индекса появляются три своих сбойных ситуации:
- открыли файл, у метастраницы которого не та магия;
- попросили предел ключей в узле, который не влезет в страницу;
Validateнашёл нарушение структуры.
Все три в эталоне это обычный fmt.Errorf с понятным текстом, без своего типа ошибки. Это сознательное решение, и в Go его стоит проговорить. Свой тип или сторожевое значение (var ErrBadMagic = errors.New(...)) нужны тогда, когда вызывающий код по-разному реагирует на разные ошибки и различает их через errors.Is или errors.As. Здесь никто не реагирует по-разному. Битая магия при открытии таблицы это повод упасть с сообщением, а нарушенный инвариант бывает только в тестах, где must.Do(tree.Validate()) уронит тест с текстом ошибки. Различать нечего, значит и тип заводить незачем. Когда свой тип ошибки всё же нужен, разобрано в уроке про ошибки.
Ошибки пула (ErrExhausted) и диска индекс не оборачивает и не перекрашивает, а возвращает как есть. Вызывающий, которому важно исчерпание пула, по-прежнему поймает его через errors.Is(err, bufferpool.ErrExhausted).
Главное решение порта: defer снимает pin, форма кода решает, сколько их
В уроке 2 мы договорились: каждое FetchPage парно с UnpinPage. В куче пары были короткими и почти всегда стояли в одной функции. В дереве всё сложнее: спуск идёт через несколько узлов, на любом из них может случиться ошибка, а вставка возвращается вверх по пути и меняет узлы на обратном ходе. Забытый UnpinPage в одной ветке с ранним return err это кадр пула, который больше никогда не освободится. Пул на 16 кадров после 16 таких утечек отвечает ErrExhausted на каждый запрос.
Go закрывает это одним инструментом: defer. Pin берём, и следующей строкой ставим defer UnpinPage. Дальше функция может вернуться откуда угодно, pin снимется. А вот сколько страниц закреплено одновременно, решает уже форма кода, и в дереве их две.
Чтение (Search, RangeScan, Height) держит один pin за раз. Весь доступ к узлу на чтение проходит через маленькую функцию visit(id, fn): закрепить, вызвать замыкание, снять pin в defer. Спуск это цикл for, а не рекурсия: на каждом шаге visit закрепляет узел, замыкание выбирает ребёнка и записывает его номер во внешнюю переменную, visit возвращается и снимает pin, и только после этого цикл идёт к ребёнку. В любой момент закреплён ровно один узел. Читающему спуску родитель после выбора ветки не нужен.
Вставка (insertInto) держит весь путь закреплённым. Она рекурсивная. Каждый вызов закрепляет свой узел, ставит defer на снятие pin и внутри себя вызывает insertInto для ребёнка. Пока ребёнок работает, кадр родителя на стеке вызовов ещё жив, и его defer ещё не сработал. На самом дне рекурсии закреплён весь путь от корня до листа, а отложенные вызовы снимают pin-ы снизу вверх, когда рекурсия разматывается. Вставке родитель нужен после возврата из ребёнка: если ребёнок расщепился, в родителя надо вставить поднятый разделитель.
Запомни этот контраст, он и есть Go-сторона урока. Один и тот же defer UnpinPage, но в цикле с visit он срабатывает на каждом шаге, а в рекурсии копится на стеке. Число одновременных pin-ов это 1 у чтения и O(высоты) у вставки. При высоте 3-4 даже скромному пулу на 8 кадров этого хватает, и это проверяет отдельный тест.
И одна ловушка defer, на которую вставка наступила бы, если бы её писали в лоб. Вставка не знает заранее, менялся ли узел: если ребёнок не расщепился, родитель остаётся чистым. Поэтому флаг dirty вычисляется по ходу, а снять pin надо с его итоговым значением. Строка defer t.pool.UnpinPage(id, dirty) здесь была бы ошибкой: аргументы отложенного вызова вычисляются в момент выполнения defer, то есть тут же, когда dirty ещё false. Изменение узла потерялось бы при вытеснении. Правильная форма это замыкание:
dirty := false
defer func() { t.pool.UnpinPage(id, dirty) }()Замыкание захватывает саму переменную dirty, а не её текущее значение, и прочитает её при выходе из функции. Ровно так это и написано в эталоне.
дальше после входа
Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.
Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.