Своя СУБД на Haskell · урок 4: B+Tree индекс

Кому это. Ты прошёл урок 3: таблица хранит строки на страницах и отдаёт их по Rid или полным сканом. Сегодня найдём строку по ключу, не поднимая всю таблицу. Тот же индекс построен в TS-треке, и формат узла байт в байт тот же. В Haskell-порте два слоя: OurDb.BTree.Node это вид на страницу как на узел, набор функций над Page без собственного состояния, а OurDb.BTree это рекурсивные алгоритмы поиска, вставки и удаления поверх пула. Главный инструмент урока рекурсия: путь от корня к листу живёт в стеке вызовов, а результат расщепления всплывает наверх значением Maybe.

Важно про код. Этот урок самый длинный по коду в первой половине воркшопа. Узел это двадцать маленьких функций, дерево это пять рекурсий. Не торопись: напиши узел, прогони тесты узла, потом дерево. Если рекурсия над деревом с возвратом значения наверх кажется непривычной, освежи урок про списки и рекурсию.

Где мы в движке

┌────────────────────────────────────────────────┐
│  Бинарный протокол + TCP-сервер                  │  урок 11
├────────────────────────────────────────────────┤
│  Исполнитель (Volcano) + EXPLAIN                 │  урок 6
│  Парсер, лексер, pretty-printer                  │  урок 5
├────────────────────────────────────────────────┤
│  Vacuum                                          │  урок 10
│  Блокировки (2PL), граф ожидания                 │  урок 9
│  MVCC, менеджер транзакций                       │  урок 8
│  WAL (журнал, redo, recovery)                    │  урок 7
├────────────────────────────────────────────────┤
│  B+Tree индекс                                   │  урок 4  ← мы здесь
│  Куча (slotted pages, seq scan)                  │  урок 3
├────────────────────────────────────────────────┤
│  Буферный пул (кэш страниц, вытеснение)           │  урок 2
│  DiskManager (страницы поверх файла)              │  урок 1
└────────────────────────────────────────────────┘

Индекс живёт в своём файле со своим пулом, рядом с кучей. Он ничего не знает про кортежи: он отображает ключ Int64 в Rid, а за строкой по этому адресу движок в уроке 6 сходит в кучу сам.

Почему именно B+Tree

На диске единица обмена это не байт и не ключ, а целая страница в 8 КБ. Прочитать один байт стоит столько же, сколько всю страницу. Двоичное дерево хранит по одному ключу в узле, и при миллионе ключей спуск к листу трогает около 20 узлов, то есть до 20 обращений к диску. Беда не в сравнениях, беда в походах на диск.

B+Tree кладёт в один узел не один ключ, а сотни, сколько влезает в страницу. Это число называется fanout, и именно он делает дерево низким. При fanout в несколько сотен миллионы ключей умещаются в три-четыре уровня, и поиск это три-четыре страницы вместо двадцати.

“Плюс” в названии означает, что значения (у нас Rid) лежат только в листьях. Внутренние узлы хранят разделители, которые говорят, в какую ветку спускаться. Отсюда два выигрыша. Внутренние узлы не тащат значения, поэтому fanout ещё выше. И листья связаны в цепочку слева направо: диапазонный запрос спускается к первому подходящему листу и дальше бежит по цепочке, не возвращаясь вверх.

Дерево всегда сбалансировано: все листья на одной глубине, и глубина растёт, только когда расщепляется корень. Балансировку дерево держит само, через расщепление переполненных узлов снизу вверх. Поиграй: вставляй ключи и смотри, как лист переполняется, делится, как разделитель всплывает наверх и как корень расщепляется.

Если повозился, ты видел три вещи, которые сейчас запрограммируешь. Лист переполняется и делится, минимальный ключ правого листа копируется наверх как разделитель. Новые листья встают в цепочку. Высота растёт только при расщеплении корня.