B-дерево

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

История

Концепция B-дерева была впервые предложена в 1972 году немецким учёным Рудольфом Байером и американским учёным Эдвардом Мак-Крейтом, работавшими в исследовательском центре корпорации Boeing. Первоначальное название было «B-tree», где буква «B», по разным версиям, могла означать «Boeing», «balanced» (сбалансированное) или «Bayer». Основной мотивацией для создания B-деревьев стала необходимость в структурах данных, оптимизированных для работы с медленной вторичной памятью (магнитными дисками), где основным узким местом является количество дисковых операций ввода-вывода. Классические сбалансированные деревья, такие как красно-чёрные или АВЛ-деревья, требовали множества операций чтения/записи небольших блоков, что было неэффективно.

B-деревья, напротив, были спроектированы так, чтобы каждый узел занимал целый блок диска, что позволяло за одну операцию ввода-вывода считывать или записывать сразу сотни ключей и указателей. Это значительно сокращало общее время работы с большими объёмами данных. В последующие десятилетия B-деревья и их вариации (B+-деревья, B*-деревья) стали стандартом де-факто для построения индексов в реляционных СУБД, таких как Oracle, PostgreSQL, MySQL (InnoDB), Microsoft SQL Server, а также во многих файловых системах (NTFS, HFS+, ext4).

Свойства и структура

B-дерево характеризуется параметром t (минимальная степень), который определяет минимальное и максимальное количество ключей и дочерних узлов.

• Каждый узел содержит упорядоченный набор ключей.
• Корневой узел может содержать от 1 до \(2t-1\) ключей.
• Любой внутренний узел (не лист и не корень) содержит от \(t-1\) до \(2t-1\) ключей.
• Любой внутренний узел, содержащий \(k\) ключей, имеет ровно \(k+1\) дочерних узлов.
• Все листовые узлы находятся на одной и той же глубине.
• B-дерево всегда сбалансировано: глубина от корня до любого листа одинакова.

Типы узлов

• Внутренний узел: содержит ключи и указатели на дочерние узлы. Ключи разделяют диапазоны значений, хранящиеся в дочерних поддеревьях.
• Листовой узел: содержит ключи и, как правило, указатели на соответствующие записи данных (или сами данные). В классической реализации B-дерева листья не имеют дочерних узлов.
• Корневой узел: особый случай узла в вершине дерева. Может быть как внутренним, так и листом (если дерево состоит из одного узла).

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

Поиск

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

Вставка

Вставка нового ключа в B-дерево также начинается от корня. Ключ вставляется в соответствующий листовой узел. Если после вставки листовой узел переполняется (содержит \(2t\) ключей), он разделяется (split):

1. Медианный ключ (средний) из переполненного узла перемещается в родительский узел.
2. Оставшиеся ключи делятся на два новых узла: левый (с меньшими ключами) и правый (с большими).
3. Процесс разделения может рекурсивно распространиться вверх к корню. Если корень разделяется, создаётся новый корень, а высота дерева увеличивается на единицу.

Характерной чертой B-дерева является то, что разделение узлов происходит только при переполнении, и оно не требует перебалансировки всего дерева. Для предотвращения каскадного разделения часто применяется стратегия _предварительного разделения_ при спуске от корня к листу: если дочерний узел, в который планируется вставка, уже полон, он разделяется сразу.

Удаление

Удаление ключа из B-дерева более сложно, чем вставка. Удаление из листового узла тривиально, если узел после удаления остаётся достаточно заполнен (не менее \(t-1\) ключа). Если же узел становится недозаполненным (underflow), применяются два действия:

• Заимствование (borrowing): ключ заимствуется из соседнего (левого или правого) братского узла через родительский узел. При этом родительский ключ перемещается в текущий узел, а один из крайних ключей братского узла перемещается на его место в родителе.
• Слияние (merging): если соседний узел не может предоставить ключ (то есть он сам содержит минимальное количество ключей), происходит слияние текущего узла с соседним. Ключ-разделитель из родителя опускается в новый объединённый узел. После слияния родительский узел теряет один ключ и одного дочернего узла, что может вызвать рекурсивное недозаполнение вверх по дереву. Если в результате слияния корень остаётся без ключей, он удаляется, а его единственный дочерний узел становится новым корнем.

Вариации B-дерева

B+-дерево

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

B*-дерево

Модификация, стремящаяся к более равномерному заполнению узлов и предотвращению частых разделений. В B*-деревьях внутренние узлы должны быть заполнены как минимум на \(2/3\), а не на \(1/2\), как в классическом B-дереве. При переполнении ключи распределяются между двумя соседними узлами, а не создаётся новый узел. Эта структура требует меньше разделений, но может потребовать больше слияний при удалении.

Критика

Несмотря на широкое распространение, B-деревья не лишены недостатков. В современных системах с быстрой оперативной памятью (RAM) и многоядерными процессорами оверхед на кэширование блоков может быть значительным. Для in-memory баз данных часто применяются другие структуры, такие как деревья Trie или хеш-таблицы. Кроме того, классические B-деревья плохо подходят для работы с конкурентным доступом (многопоточность), требуя сложных механизмов блокировок. Для решения этой проблемы были разработаны B-link-деревья с использованием фиксации (latch-free) алгоритмов.

Тем не менее, для задач, где основным ограничением является скорость ввода-вывода на диске или твердотельном накопителе (SSD), B-деревья остаются одним из наиболее эффективных и надёжных решений.

Пример (t=2)

Рассмотрим B-дерево с минимальной степенью \(t=2\). Максимальное количество ключей в узле: \(2t-1 = 3\). Узел может иметь от 2 до 4 дочерних узлов.

Пусть дерево содержит ключи: [10, 20, 30] в корне, а у корня три дочерних узла:

• Левый: [5, 7]
• Средний: [15, 17, 19]
• Правый: [25, 27]

При вставке ключа 22:

1. Поиск в корне определяет, что 22 попадает в средний диапазон (между 20 и 30).
2. Спуск в средний дочерний узел [15, 17, 19].
3. Вставка 22 в этот узел приведёт к переполнению, так как он содержит 3 ключа, а после вставки стало бы 4. Выполняется разделение:

• Медианный ключ (17) отправляется в корень.
• Левый узел: [15]
• Правый узел: [19, 22]

1. Корень теперь содержит [10, 17, 20, 30].
2. У корня становится 5 дочерних узлов, что нарушает ограничение (\(t=2 \Rightarrow\) до 4 дочерних). Выполняется разделение корня:

• Медианный ключ (17) становится новым корнем.
• Левый узел: [10]
• Правый узел: [20, 30]

1. Дерево стало глубиной 2.

Применение

B-деревья и их вариации являются фундаментом для многих систем, работающих с упорядоченными данными:

• Реляционные базы данных: используются для построения кластеризованных и некластеризованных индексов на столбцах таблиц. Индекс на основе B+-дерева позволяет быстро находить строки по значению ключа.
• Файловые системы: NTFS (индекс $MFT), HFS+, XFS, EXT4 используют B-подобные деревья для каталогов и управления экстентами.
• NoSQL-базы данных: некоторые системы, такие как MongoDB (индексы по умолчанию) и CouchDB, используют B-деревья для индексации.
• In-memory кэши и словари: библиотеки реализуют B-деревья для обеспечения быстрой вставки и поиска в памяти, хотя для чисто оперативной памяти они менее популярны, чем хеши или Trie.

Источники

1. Bayer, R.; McCreight, E. M. (1972). «Organization and Maintenance of Large Ordered Indices». Acta Informatica 1: 173–189.
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
3. Wirth, N. (1985). Algorithms and Data Structures. Prentice-Hall.
4. Graefe, G. (2011). «Modern B-Tree Techniques». Foundations and Trends in Databases. 3 (4): 203–402.