B-дерево: вставка ключа и разделение узла

B-дерево - сильно ветвящееся сбалансированное дерево поиска, спроектированное Байером и Маккрейтом в 1972 году для индексов на внешних носителях. В отличие от AVL и красно-чёрных деревьев, где в узле один ключ, узел B-дерева содержит десятки или сотни ключей. Высота получается крошечной - единицы уровней даже на миллиардах записей, - а операции укладываются в $O(\log n)$ обращений к диску. Вставка опирается на одну идею: если узел переполнился, он расщепляется надвое, а средний ключ поднимается к родителю.

Определение B-дерева порядка t

B-дерево с минимальной степенью $t \ge 2$ - это сбалансированное по высоте дерево поиска, в котором каждый узел, кроме корня, содержит от $t-1$ до $2t-1$ ключей. Корень допускает от $1$ до $2t-1$ ключей. Если узел содержит $k$ ключей, у него ровно $k+1$ ссылок на детей; ключи внутри узла упорядочены по возрастанию.

Для каждого внутреннего узла с ключами $k_1 < k_2 < \dots < k_m$ и детьми $c_0, c_1, \dots, c_m$ все ключи в поддереве $c_i$ лежат в интервале $(k_i, k_{i+1})$. Все листья находятся на одной глубине - это и есть свойство сбалансированности высоты, оно поддерживается алгоритмом вставки и удаления автоматически.

Параметр $t$ называют минимальной степенью. Иногда вместо $t$ задают «порядок» $m = 2t$ - максимальное число детей; обе формы эквивалентны.

Свойство сбалансированности и оценка высоты

Из инварианта $t-1 \le \text{ключей} \le 2t-1$ следует жёсткая оценка высоты:

$h \le \log_t \frac{n+1}{2}.$

Для $t = 100$ и $n = 10^9$ это даёт $h \le 4{,}5$ - пять уровней на миллиард записей. Любая операция спускается по одному пути от корня к листу, число обращений к диску - порядка высоты.

Зачем такое сильное ветвление: блочное чтение с диска

B-дерево создавалось под физику внешней памяти, и форма узла привязана к размеру дискового блока (или страницы СУБД - 4–16 КБ для PostgreSQL, 16 КБ по умолчанию в InnoDB MySQL). Один узел упаковывают так, чтобы он целиком влез в один блок: один seek - десятки и сотни сравнений в RAM. AVL и RB на диске страдают от того, что каждый узел - отдельный блок ради двух-трёх ключей.

Отсюда выбор $t$: его задают так, чтобы $2t-1$ ключей плюс служебные ссылки заполняли страницу. На практике $t$ - десятки и сотни, а не двойки-тройки из учебных примеров.

Соберите дерево из последовательности вставок или прогоните одну операцию пошагово - tool вернёт промежуточные состояния, точки переполнения и список произошедших разделений.

Алгоритм вставки

Вставка в B-дерево похожа на вставку в BST, но с двумя отличиями: спуск идёт по «толстым» узлам, а переполнение чинится разделением.

1. Поиск листа. Идём от корня. В каждом узле находим позицию нового ключа (бинарным поиском) и спускаемся в соответствующего ребёнка. Останавливаемся, дойдя до листа.
2. Локальная вставка. Ключ помещается в лист на нужную позицию, существующие ключи сдвигаются вправо.
3. Split при переполнении. Если в листе стало $2t$ ключей, средний ключ $k_t$ поднимается в родителя; узел разбивается на два - левый получает первые $t-1$ ключей, правый - последние $t-1$.
4. Каскад. Если родитель тоже переполнился, операция повторяется выше. В худшем случае разделения доходят до корня - тогда из его среднего ключа создаётся новый корень. Это единственный способ увеличить высоту B-дерева, поэтому все листья остаются на одной глубине.

На практике используют проактивный split: при спуске, прежде чем войти в ребёнка с $2t-1$ ключами, его сразу делят. Вставка работает за один спуск, без обратного хода, и хорошо ложится на буфер-менеджер СУБД.

Пример: вставка 10, 20, 5, 6, 12, 30, 7, 17 при $t=2$

При $t=2$ узел держит от 1 до 3 ключей. Стартуем с пустого дерева.

• Вставки 10, 20, 5 - все в корень: [5, 10, 20].
• Вставка 6: получаем 4 ключа - переполнение. Средний ключ 10 поднимается, корень делится. Новое дерево: корень [10], дети [5, 6] и [20].
• Вставки 12, 30: правый ребёнок становится [12, 20, 30] - заполнен, но ещё не переполнен.
• Вставка 7: спуск в левый ребёнок, получаем [5, 6, 7].
• Вставка 17: правый ребёнок переполняется до [12, 17, 20, 30]. Средний ключ 20 поднимается в корень; правый узел делится на [12, 17] и [30]. Корень становится [10, 20], у него три ребёнка.

Высота выросла на один уровень один раз - при первом split. Дальше дерево расширяется в ширину, что и обеспечивает $O(\log_t n)$.

Удаление: краткий обзор

Удаление опирается на зеркальный приём - слияние недополненного узла с соседом. Если ключ лежит в листе с $\ge t$ ключами - удаляем напрямую. Иначе перед удалением:

• Rotation (borrow). У соседнего листа есть запас ($\ge t$ ключей) - забираем у него один ключ через родителя.
• Merge. Соседи бедные - два листа сливаются в один с разделяющим их ключом из родителя; в родителе становится на ключ меньше, и проблема может всплыть наверх.

Для внутреннего узла ключ заменяют на предшественника или преемника из листа - и удаляют его из листа. Сложность - $O(\log_t n)$.

Варианты: B+-дерево и B*

B-дерево из 1972 года почти не используется в чистом виде - его вытеснили варианты.

• B+-дерево. Полезные данные хранят только в листьях, а внутренние узлы содержат лишь ключи-разделители. Листья соединены в двусвязный список - диапазонный скан WHERE x BETWEEN a AND b идёт линейным проходом по листьям без возврата к корню. Это формат большинства СУБД-индексов: PostgreSQL btree, MySQL InnoDB, SQL Server, Oracle.
• B*-дерево.** Усиленный B+: узлы перед split пытаются перераспределить ключи с соседом, каждый узел держит не менее $2/3$ от максимума. Дерево ещё плотнее. Используется в HFS+ и Reiser4.

Применение и сравнение с AVL, RB и B+

Где живут B-деревья на практике:

• СУБД-индексы. PostgreSQL (btree по умолчанию), MySQL InnoDB (clustered primary key), Oracle, SQL Server, SQLite - все на B+.
• Файловые системы. NTFS хранит каталоги в B+, HFS+ - в B*, APFS - в B-tree с copy-on-write, Btrfs (само имя) и ext4 (htree-каталоги).
• Key-value хранилища. WiredTiger (движок MongoDB), LMDB - на B+ с copy-on-write страницами.

AVL и RB выигрывают в RAM на малых $n$ за счёт простоты и кэш-локальности, B-дерево и его варианты - на диске и больших объёмах за счёт ширины узла.

Типовые учебные задачи: построить B-дерево с $t=2$ из последовательности 1..10 и нарисовать промежуточные состояния; показать, какие узлы разделятся при вставке очередного ключа и поднимется ли split до корня; найти минимальное и максимальное число ключей в B-дереве высоты $h$ при заданном $t$; различить, когда удаление вызовет merge, а когда rotation у соседа.

Частые ошибки

• Путают порядок $m$ и минимальную степень $t$. В одних учебниках $m$ - максимальное число детей ($m = 2t$), в других - максимальное число ключей ($m = 2t-1$). Перед задачей всегда уточняйте определение.
• Поднимают не средний ключ при split. Должна подниматься именно медиана; иначе ломается инвариант «$t-1$ ключей в каждом узле, кроме корня».
• Считают, что split всегда увеличивает высоту. Высота растёт только когда делится сам корень. На любом другом уровне split увеличивает ширину родителя, а не глубину.
• Сравнивают B-дерево с AVL по числу узлов. Корректная метрика - число обращений к диску, и тут B-дерево заведомо в выигрыше при большом $t$.
• Используют B-дерево в RAM. Для in-memory словарей оно почти всегда проигрывает RB или хеш-таблицам. B-дерево раскрывается только на диске или на NVMe с большими страницами.

FAQ

Чем B-дерево отличается от двоичного дерева поиска? В BST один ключ на узел и две ссылки; в B-дереве - $t-1$ до $2t-1$ ключей и до $2t$ ссылок. Высота B-дерева пропорциональна $\log_t n$, а не $\log_2 n$, и обращений к диску на порядок меньше - это и было мотивацией Байера и Маккрейта в 1972 году.

Почему вставка работает за $O(\log n)$, если split может всплыть до корня? Число split за одну вставку не превосходит высоты дерева, то есть $O(\log_t n)$ штук. Каждое разделение делает $O(t)$ работы в RAM, но обращений к диску ровно $O(\log_t n)$ - а на диске именно это считается за «стоимость» операции.

В чём разница между B-деревом и B+-деревом? В B-дереве данные могут лежать как во внутренних узлах, так и в листьях. В B+ данные - только в листьях, а листья связаны в список. Это даёт два выигрыша: внутренние узлы плотнее (туда влезает больше ключей-разделителей), и range-сканы идут линейным проходом по листьям. Поэтому реальные СУБД используют B+.

Коротко

B-дерево - это сбалансированное дерево поиска, где каждый узел хранит от $t-1$ до $2t-1$ ключей и упакован в один дисковый блок. Вставка идёт спуском к листу, локальной вставкой и, при переполнении, разделением узла с подъёмом среднего ключа в родителя; в худшем случае split каскадно доходит до корня - это единственный способ увеличить высоту. За счёт большого $t$ высота получается крошечной, операции стоят $O(\log_t n)$ обращений к диску, и поэтому B-дерево и его наследники (B+ в PostgreSQL, MySQL InnoDB, NTFS; B* в HFS+) остаются стандартом индексов для внешней памяти уже полвека.