B*-дерево

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

История и предпосылки создания

B-деревья были впервые описаны Рудольфом Байером и Эдвардом МакКрейтом в 1970 году. Они решали проблему эффективного хранения и поиска больших объёмов данных на медленных запоминающих устройствах, таких как магнитные диски. Основной недостаток классических B-деревьев — возможность появления узлов с низкой заполненностью (до 50 %), что приводило к нерациональному использованию дискового пространства и увеличению высоты дерева.

В 1973 году Дональд Кнут в своей книге «Искусство программирования» предложил модификацию B-дерева, названную B*-деревом. Основная идея заключалась в том, чтобы при переполнении узла не разделять его на два, а перераспределять ключи между соседними узлами. Это позволило повысить минимальный коэффициент заполнения узла с 50 % до 66 %, а в некоторых реализациях — до 90 %.

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

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

Основные свойства

• Сбалансированность: Все листья находятся на одном уровне, что гарантирует логарифмическую сложность поиска.
• Упорядоченность: Ключи в узле хранятся в отсортированном порядке. Для каждого узла все ключи в левом поддереве меньше ключа узла, а в правом — больше.
• Высокая заполненность: Минимальная заполненность узла составляет 2/3 от максимальной ёмкости, что снижает высоту дерева по сравнению с B-деревом при одинаковом количестве данных.
• Перераспределение ключей: При вставке ключа в переполненный узел (количество ключей достигло максимума) сначала предпринимается попытка перераспределить часть ключей в соседний узел (братский). Если оба узла переполнены, происходит разделение на три узла.

Операции с B*-деревом

Поиск

Поиск в B*-дереве выполняется так же, как и в B-дереве. Начиная с корня, алгоритм последовательно сравнивает искомый ключ с ключами в узле и переходит в соответствующее поддерево. Сложность поиска составляет O(log n), где n — количество ключей в дереве.

Вставка

Вставка нового ключа является более сложной операцией, чем в B-дереве, из-за механизма перераспределения. Алгоритм:

1. Найти лист, в который должен быть вставлен ключ.
2. Если лист не заполнен (количество ключей меньше максимума), вставить ключ в упорядоченное место.
3. Если лист заполнен, проверить соседние узлы (левый и правый братские узлы).
4. Если один из братских узлов не заполнен, выполнить перераспределение: часть ключей из переполненного узла перемещается в братский узел, а разделяющий ключ в родительском узле корректируется.
5. Если оба братских узла заполнены, выполнить разделение: переполненный узел и один из братских узлов (обычно правый) делятся на три узла, каждый из которых заполнен примерно на 2/3. Средний ключ при этом поднимается в родительский узел.
6. Если родительский узел также переполнен, процесс рекурсивно повторяется для него.

Удаление

Удаление ключа также может потребовать перераспределения или слияния узлов. Если после удаления ключа в узле остаётся меньше минимального количества ключей (2/3 от максимума), предпринимается попытка заимствовать ключ из соседнего узла. Если это невозможно, выполняется слияние узлов.

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

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

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

Недостатки

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

Применение

B*-деревья нашли широкое применение в системах, где требуется высокая производительность операций с данными на дисковых носителях:

• Системы управления базами данных (СУБД): Многие современные СУБД, такие как Oracle, PostgreSQL, MySQL (InnoDB), используют B-деревья (или их варианты) для построения индексов. Например, в PostgreSQL для индексов типа B-tree используется модификация, близкая к B-дереву.
• Файловые системы: Некоторые файловые системы, например, HFS+ (macOS) и ReiserFS, применяют B*-деревья для организации каталогов и метаданных.
• Операционные системы: В некоторых операционных системах B*-деревья используются для управления виртуальной памятью и кэшированием.

Варианты и модификации

Существует несколько модификаций B*-деревьев, направленных на улучшение их характеристик:

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

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

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

Источники

1. Bayer, R., & McCreight, E. (1970). Organization and maintenance of large ordered indexes. Proceedings of the 1970 ACM SIGFIDET Workshop on Data Description and Access.
2. Knuth, D. E. (1973). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.
3. Comer, D. (1979). Ubiquitous B-tree. ACM Computing Surveys (CSUR), 11(2), 121-137.
4. Graefe, G. (2010). Modern B-tree techniques. Foundations and Trends in Databases, 3(4), 373-518.
5. Документация PostgreSQL. Chapter 11. Indexes. 11.2. B-Tree Indexes.