B+-дерево

B+‑дерево — это структура данных, представляющая собой самобалансирующееся дерево поиска, в котором все ключи хранятся в листьях, а внутренние узлы служат исключительно для маршрутизации. Относится к классу многоуровневых индексных структур, используемых в системах управления базами данных (СУБД) и файловых системах для обеспечения эффективного доступа к данным на дисковых носителях. B+‑дерево является вариантом B‑дерева, отличающимся строгим разделением ролей между внутренними и листовыми узлами, что позволяет оптимизировать операции вставки, удаления и поиска при работе с большими объёмами данных.

История

B+‑деревья были впервые описаны в 1970‑х годах как развитие концепции B‑деревьев, предложенной Рудольфом Байером и Эдвардом Маккейтом в 1972 году. Основной целью создания B+‑дерева стало повышение эффективности последовательного доступа к данным, который в классических B‑деревьях требовал обхода множества уровней. Идея заключалась в том, чтобы все ключи и связанные с ними данные (или указатели на данные) сосредоточить только в листовых узлах, а внутренние узлы сделать «направляющими» — содержащими только ключи для навигации. Такой подход позволил значительно ускорить операции сканирования диапазонов и полного перебора записей.

Первые реализации B+‑деревьев появились в коммерческих СУБД в конце 1970‑х — начале 1980‑х годов. Одной из наиболее известных ранних систем, использующих B+‑деревья, стала IBM System R. Впоследствии структура стала стандартом де‑факто для построения индексов в реляционных СУБД, таких как Oracle, PostgreSQL, MySQL (InnoDB) и Microsoft SQL Server. Также B+‑деревья применяются в файловых системах (например, NTFS, ReiserFS, Btrfs) и в некоторых NoSQL‑системах (например, Couchbase).

Устройство и свойства

Структура узлов

B+‑дерево состоит из двух типов узлов: внутренних (индексных) и листовых. Каждый узел содержит упорядоченный набор ключей и указателей на дочерние узлы (или на данные). Количество ключей в узле ограничено параметром порядка (обычно обозначается как t или m). В большинстве реализаций каждый узел, кроме корневого, должен содержать не менее ceil(m/2) ключей (условие полузаполненности), что гарантирует сбалансированность дерева.

• Внутренние узлы содержат k ключей и k+1 указателей на дочерние узлы. Ключи в таких узлах используются только для направления поиска: все ключи в поддереве, на которое указывает i‑й указатель, меньше или равны i‑му ключу, а ключи в поддереве, на которое указывает (i+1)‑й указатель, больше i‑го ключа.
• Листовые узлы содержат полные записи ключей и связанные с ними данные (либо указатели на строки данных). Листовые узлы связаны между собой в односвязный или двусвязный список, что позволяет выполнять последовательное сканирование без подъёма по дереву.

Высота и балансировка

Высота B+‑дерева (количество уровней от корня до листьев) логарифмически зависит от количества ключей и порядка узлов. Для дерева с миллионами записей высота обычно составляет 3–5 уровней, что делает операции поиска, вставки и удаления очень быстрыми даже при работе с медленными дисковыми накопителями. Автоматическая балансировка поддерживается за счёт расщепления узлов при переполнении и слияния узлов при недозаполнении.

Основные операции

• Поиск — начинается с корневого узла; на каждом уровне выбирается подходящий дочерний узел по сравнению ключей. Поиск завершается в листовом узле, где находится искомый ключ (или фиксируется его отсутствие). Время поиска — O(log_m n).
• Вставка — сначала выполняется поиск листового узла, куда должен быть помещён новый ключ. Если в узле есть свободное место, ключ вставляется с сохранением упорядоченности. Если узел переполнен (содержит m ключей), он расщепляется на два узла, а средний ключ перемещается в родительский узел. Расщепление может рекурсивно распространяться вверх, вплоть до корня (при необходимости создаётся новый корень).
• Удаление — аналогично вставке, сначала находится листовой узел с удаляемым ключом. После удаления проверяется условие полузаполненности. Если количество ключей в узле становится меньше ceil(m/2), выполняется слияние с соседним узлом или перераспределение ключей между узлами. При слиянии может потребоваться удаление ключа из родительского узла, что также может рекурсивно распространяться.
• Последовательное сканирование — благодаря списку листовых узлов можно быстро перебрать все ключи в порядке возрастания, двигаясь по ссылкам от одного листа к другому без дополнительных операций поиска.

Классификация и варианты

B+‑деревья могут различаться по следующим параметрам:

• Порядок дерева (m) — максимальное количество ключей в узле. Выбор порядка зависит от размера блока на диске и размера ключа. Типичные значения — от 100 до 1000.
• Тип связи между листьями — односвязный или двусвязный список. Двусвязный список упрощает обратное сканирование, но требует дополнительной памяти для хранения указателей.
• Хранение данных — данные могут храниться непосредственно в листовых узлах (кластеризованные индексы) или в виде указателей на строки таблицы (некластеризованные индексы).
• Поддержка дубликатов — некоторые реализации допускают хранение нескольких записей с одинаковыми ключами (например, в индексах с неуникальными ключами).

Существуют также модификации B+‑деревьев, такие как B*‑деревья (с более строгим распределением ключей) и B‑link‑деревья (с поддержкой конкурентного доступа без блокировок).

Применение

Системы управления базами данных

B+‑деревья являются основным типом индексов в большинстве реляционных СУБД. Они используются для ускорения операций SELECT, JOIN, ORDER BY и GROUP BY. Например, в MySQL (движок InnoDB) первичный ключ хранится как кластеризованный B+‑дерево, а вторичные индексы — как некластеризованные B+‑деревья. В PostgreSQL B+‑деревья применяются для индексов типа B‑tree (фактически B+‑tree).

Файловые системы

В файловых системах B+‑деревья используются для организации каталогов и управления распределением дискового пространства. Например, в NTFS метаданные файлов хранятся в структуре, основанной на B+‑деревьях. В Btrfs B+‑деревья применяются для всех ключевых структур: экстентов, инодов, контрольных сумм.

NoSQL‑системы

Некоторые NoSQL‑системы, такие как Couchbase, используют B+‑деревья для индексации документов. В MongoDB B‑деревья (фактически B+‑деревья) применяются в индексах по умолчанию.

Преимущества и недостатки

Преимущества

• Высокая производительность поиска — логарифмическая сложность O(log n) с очень малым коэффициентом (высота дерева редко превышает 4–5).
• Эффективность при работе с диском — узлы обычно соответствуют размеру блока (4–16 КБ), что минимизирует количество операций ввода‑вывода.
• Поддержка последовательного доступа — список листьев позволяет быстро сканировать диапазоны ключей.
• Автоматическая балансировка — дерево остаётся сбалансированным после вставок и удалений.
• Устойчивость к сбоям — многие реализации поддерживают журналирование и восстановление.

Недостатки

• Избыточность памяти — внутренние узлы занимают дополнительное место, хотя и не хранят данные.
• Сложность реализации — операции расщепления и слияния требуют аккуратного кодирования.
• Ограниченная поддержка частичных совпадений — B+‑деревья оптимизированы для точного поиска и поиска по префиксу, но не для полнотекстового поиска или поиска по шаблону с масками.
• Необходимость реорганизации — при частых вставках и удалениях может потребоваться периодическая перестройка индекса.

Примеры использования

• Индекс первичного ключа в MySQL (InnoDB) — кластеризованное B+‑дерево, где листовые узлы содержат полные строки таблицы.
• Каталог файлов в NTFS — B+‑дерево хранит имена файлов и ссылки на их метаданные (MFT‑записи).
• Индекс в PostgreSQL — B‑tree индекс, реализованный как B+‑дерево с возможностью хранения дубликатов.
• Индекс в Couchbase — B+‑дерево используется для быстрого поиска документов по ключу.

Интересные факты

• Название «B‑дерево» не расшифровывается однозначно: по одной версии, буква B означает «балансированное» (balanced), по другой — «Bayer» (в честь одного из авторов), по третьей — «Boeing» (компания, в которой работали авторы). Для B+‑дерева буква «+» указывает на наличие дополнительной связи между листьями.
• B+‑деревья лежат в основе многих современных СУБД, включая Oracle, MySQL, PostgreSQL, SQLite, MongoDB и Couchbase.
• В некоторых СУБД (например, SQL Server) B+‑деревья используются не только для индексов, но и для организации хранения самих таблиц (кластеризованные таблицы).
• В файловой системе Btrfs B+‑деревья применяются для всех метаданных, что позволяет выполнять операции с файлами за O(log n) время.

Источники

• Bayer, R., & McCreight, E. (1972). Organization and Maintenance of Large Ordered Indices. Acta Informatica, 1(3), 173–189.
• Comer, D. (1979). Ubiquitous B‑Tree. ACM Computing Surveys, 11(2), 121–137.
• Silberschatz, A., Korth, H. F., & Sudarshan, S. (2019). Database System Concepts (7th ed.). McGraw‑Hill.
• Graefe, G. (1993). Query Evaluation Techniques for Large Databases. ACM Computing Surveys, 25(2), 73–170.
• Документация PostgreSQL: B‑Tree Indexes.
• Документация MySQL: InnoDB Index Structures.