B+-деревья

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

История

B-деревья были впервые описаны Рудольфом Байером и Эдвардом МакКрейтом в 1970 году в работе «Organization and Maintenance of Large Ordered Indexes». В 1972 году Дуглас Комер предложил модификацию, получившую название B+-дерево. Основное отличие заключалось в том, что все данные были вынесены в листовые узлы, а внутренние узлы стали выполнять исключительно роль навигационных указателей. Это позволило значительно увеличить коэффициент ветвления (количество дочерних узлов) и, как следствие, уменьшить высоту дерева при том же объёме данных. B+-деревья стали стандартом де-факто для построения индексов в реляционных СУБД, таких как Oracle, MySQL, PostgreSQL, а также в файловых системах (например, NTFS, ReiserFS).

Устройство и принцип работы

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

Внутренние узлы

Внутренние узлы содержат только ключи-разделители и указатели на дочерние узлы. Ключ-разделитель в внутреннем узле определяет диапазон значений, которые могут находиться в соответствующем поддереве. Например, если внутренний узел содержит ключи k1, k2, ..., kn, то первый дочерний узел содержит ключи, меньшие k1, второй — ключи от k1 до k2, и так далее, последний — ключи, большие или равные kn. Внутренние узлы не хранят сами записи данных.

Листовые узлы

Листовые узлы содержат все ключи и соответствующие им указатели на записи данных (или сами записи, если дерево используется как кластерный индекс). В классической реализации листовые узлы также содержат указатель на следующий листовой узел (соседний справа), что позволяет эффективно выполнять последовательный обход данных (range scan). Листовые узлы образуют односвязный или двусвязный список.

Высота дерева

Высота B+-дерева (количество уровней от корня до листьев) логарифмически зависит от количества записей и обратно пропорциональна логарифму коэффициента ветвления. Например, при коэффициенте ветвления 1000 (то есть каждый внутренний узел указывает на 1000 дочерних узлов) дерево высотой 3 может хранить до 1 миллиарда записей (1000^3). Это делает B+-деревья крайне эффективными для дисковых операций, где основное время тратится на чтение блоков данных.

Операции

Поиск

Поиск элемента по ключу начинается с корня. На каждом уровне алгоритм определяет, в какой дочерний узел перейти, сравнивая искомый ключ с ключами-разделителями в текущем узле. Процесс повторяется до тех пор, пока не будет достигнут листовой узел. В листовом узле выполняется линейный или бинарный поиск по ключам. Если ключ найден, возвращается указатель на запись; в противном случае — признак отсутствия.

Вставка

Вставка нового ключа начинается с поиска листового узла, в который должен быть помещён ключ. Если в листовом узле есть свободное место, ключ вставляется с сохранением порядка. Если узел переполнен (количество ключей превышает m), он разделяется на два узла. Средний ключ (медиана) перемещается в родительский узел. Разделение может распространяться вверх по дереву, вплоть до корня. Если корень разделяется, создаётся новый корень, и высота дерева увеличивается на 1.

Удаление

Удаление ключа также начинается с поиска в листовом узле. Если после удаления ключа узел становится «слишком пустым» (количество ключей меньше ceil(m/2)), выполняется перебалансировка. Сначала проверяется возможность заимствования ключа у соседнего узла (левого или правого). Если заимствование невозможно, производится слияние узла с соседом. При слиянии ключи объединяются, и соответствующий ключ-разделитель удаляется из родительского узла. Слияние может распространяться вверх по дереву.

Сравнение с B-деревом

Основное отличие B+-дерева от B-дерева заключается в том, что в B-дереве данные могут храниться как в листовых, так и во внутренних узлах. В B+-дереве данные хранятся только в листьях. Это приводит к следующим преимуществам:

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

Недостатком B+-дерева является несколько больший расход памяти на хранение дублирующихся ключей (ключи во внутренних узлах повторяются в листьях).

Применение

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

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

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

Некоторые файловые системы используют B+-деревья для организации каталогов и метаданных. Например, NTFS использует B+-деревья для хранения записей в корневом каталоге и для индексации атрибутов файлов. ReiserFS (использовалась в Linux) также применяла B+-деревья для хранения как файлов, так и каталогов.

Другие области

B+-деревья применяются в системах полнотекстового поиска, в NoSQL-базах данных (например, CouchDB, MongoDB), в системах управления версиями (Git использует похожую структуру для хранения объектов), а также в некоторых реализациях кэширования и индексации в оперативной памяти.

Критика и ограничения

• Сложность реализации: поддержание баланса при вставке и удалении требует сложных алгоритмов разделения и слияния узлов.
• Фрагментация: при частых вставках и удалениях листовые узлы могут становиться фрагментированными, что снижает производительность последовательного обхода.
• Неоптимальность для оперативной памяти: для данных, полностью помещающихся в оперативную память, B+-деревья могут уступать по производительности другим структурам, например, хеш-таблицам или бинарным деревьям поиска, из-за большего количества операций сравнения.
• Ограниченная поддержка многомерных данных: B+-деревья эффективны только для одномерных ключей. Для многомерных данных используются специализированные структуры, такие как R-деревья или kd-деревья.

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

• В B+-деревьях, как и в B-деревьях, буква «B» в названии не имеет однозначной расшифровки. Рудольф Байер упоминал, что она может означать «Bayer», «Boeing» (компания, в которой работали авторы), «balanced» (сбалансированное) или «broad» (широкое).
• В некоторых реализациях B+-деревьев листовые узлы могут хранить не только ключи, но и сами записи данных, что позволяет избежать дополнительного обращения к таблице.
• В современных СУБД B+-деревья часто комбинируются с буферным кэшем, который хранит наиболее часто используемые узлы в оперативной памяти, что значительно ускоряет операции.

Источники

• Байер Р., МакКрейт Э. «Organization and Maintenance of Large Ordered Indexes» (1970)
• Комер Д. «The Ubiquitous B-Tree» (1979)
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (3-е издание), глава 18
• Гарсиа-Молина Г., Ульман Дж., Уидом Дж. «Системы баз данных. Полный курс»