Как устроен алгоритм B-tree

Что проверяют

Понимаете ли вы, зачем дереву много ключей в узле и почему именно эта структура стоит под индексами баз данных. Следом обычно просят рассказать про разбиение узла при вставке и объяснить разницу между B-tree и B+tree.

Как отвечать

B-tree это сбалансированное дерево поиска, где узел хранит не один ключ, а отсортированный массив ключей и указатели на детей между ними. У дерева порядка m:

• узел: до m детей и до m-1 ключей, каждый узел, кроме корня, заполнен хотя бы наполовину;
• листья: все на одной глубине, поэтому высота примерно log_m n. При узле на сотни ключей миллион записей укладывается в три-четыре уровня;
• поиск: внутри узла бинарный или линейный поиск по ключам, затем спуск в нужного ребёнка;
• вставка: ключ кладётся в лист. Если лист переполнен, он делится пополам, средний ключ поднимается в родителя. Деление может дойти до корня, тогда дерево вырастает на уровень сверху;
• удаление: при недозаполнении узел занимает ключ у соседа или сливается с ним.

Главная идея: узел подгоняется под размер страницы диска или под кеш процессора. Сравнений внутри узла много, но они дешёвые, а дорогих чтений страниц мало. Асимптотика O(log n) та же, что у красно-чёрного дерева, но на диске B-tree выигрывает за счёт числа обращений к страницам.

Дальше назовите B+tree: данные лежат только в листьях, листья связаны списком, внутренние узлы хранят лишь ключи-разделители. Так устроены индексы PostgreSQL и InnoDB, а в мире Go хранилище bbolt, на котором работает etcd. Для структуры в памяти в Go есть github.com/google/btree с дженерик-версией BTreeG: она нужна, когда требуется упорядоченный обход или поиск по диапазону, чего встроенный map не даёт.

Где спотыкаются

Расшифровывают «B» как «binary» и описывают двоичное дерево поиска. Это другая структура, а весь смысл B-tree как раз в сильном ветвлении.

Не могут объяснить, почему не хэш-таблица. Хэш не держит порядок, поэтому не обслуживает диапазоны, ORDER BY и поиск по префиксу.

Путают B-tree и B+tree или считают, что в базе используется «чистый» B-tree. Для сканирования диапазона важен именно связный список листьев.