B-tree¶

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

¶История

Концепция B-tree была впервые предложена Рудольфом Байером (Rudolf Bayer) и Эдвардом МакКрейтом (Edward McCreight) в 1970 году в работе «Organization and Maintenance of Large Ordered Indices». Разработка велась в исследовательской лаборатории компании Boeing. Название «B-tree» не имеет однозначной расшифровки: по утверждению авторов, буква «B» может означать «Bayer», «Boeing», «balanced» (сбалансированное) или «broad» (широкое) — в зависимости от контекста. Первоначально структура создавалась для эффективной работы с данными на магнитных дисках, где время доступа к блоку данных значительно превышает время обработки в оперативной памяти.

С 1970-х годов B-tree стала основой для организации индексов в большинстве реляционных СУБД, включая Oracle, IBM DB2, Microsoft SQL Server и PostgreSQL. В 1979 году Дуглас Комер (Douglas Comer) опубликовал обзорную статью, систематизировавшую известные варианты B-tree, что способствовало её популяризации. В последующие десятилетия появились многочисленные модификации, включая B+-tree, B*-tree и UB-tree.

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

B-tree является обобщением двоичного дерева поиска (binary search tree). В отличие от двоичного дерева, каждый узел B-tree может содержать от t-1 до 2t-1 ключей (где t — параметр, называемый минимальной степенью дерева, t ≥ 2) и, соответственно, от t до 2t потомков. Дерево всегда остаётся сбалансированным: все листья находятся на одинаковой глубине.

Формальные свойства B-tree (по определению Байера и МакКрейта):

1. Каждый узел содержит от t-1 до 2t-1 ключей (корень может содержать от 1 до 2t-1 ключей).
2. Каждый внутренний узел (не лист) имеет на один потомок больше, чем количество ключей.
3. Ключи в узле хранятся в отсортированном порядке.
4. Для каждого узла все ключи в левом поддереве меньше ключа в узле, а в правом — больше (свойство дерева поиска).
5. Все листья находятся на одной глубине (высота дерева одинакова для всех листьев).

Высота B-tree с n ключами и минимальной степенью t составляет O(log_t n). Для типичных значений t (например, t=100) высота даже для миллиардов записей не превышает 3-4 уровней, что обеспечивает малое количество дисковых операций при поиске.

¶Устройство и операции

¶Структура узла

Узел B-tree обычно состоит из:

• массива ключей (упорядоченных по возрастанию);
• массива указателей на дочерние узлы (для внутренних узлов);
• флага, указывающего, является ли узел листом;
• счётчика текущего количества ключей в узле.

В реализации для работы с диском каждый узел соответствует одному блоку (странице) фиксированного размера (например, 4 КБ или 8 КБ). Размер блока определяет максимальное количество ключей, которое может храниться в одном узле.

¶Поиск

Поиск ключа k начинается с корня. В каждом узле выполняется бинарный или линейный поиск среди ключей узла. Если ключ найден, операция завершается. Если нет — выбирается соответствующий дочерний узел (по номеру интервала между ключами) и процесс повторяется. Поиск продолжается до тех пор, пока ключ не будет найден или не будет достигнут лист, где ключ отсутствует.

¶Вставка

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

¶Удаление

Удаление ключа из B-tree — более сложная операция, чем вставка. Она требует обеспечения того, чтобы после удаления узел не оказался пустым (содержал менее t-1 ключей). Если узел становится «недозаполненным», применяются следующие стратегии:

• Заимствование (borrow): если у соседнего брата есть лишний ключ, один ключ передаётся через родителя.
• Слияние (merge): если у соседнего брата нет лишних ключей, узел сливается с братом, а ключ из родителя опускается в объединённый узел.

Слияние может распространяться вверх, и в крайнем случае высота дерева уменьшается.

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

¶B+-tree

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

¶B*-tree

Вариант, в котором узлы всегда заполнены не менее чем на 2/3 (вместо 1/2 в классическом B-tree). При разделении узла два соседних узла перераспределяют ключи, что уменьшает количество операций разделения. B*-tree реже используется на практике, чем B+-tree.

¶UB-tree (Universal B-tree)

Модификация, предназначенная для многомерных данных (пространственных индексов). Использует Z-порядок (кривую Гильберта) для отображения многомерных точек в одномерное пространство, после чего применяет стандартную B-tree.

¶R-tree

Не является прямым потомком B-tree, но использует схожие принципы балансировки и разделения узлов. R-tree предназначена для индексации многомерных прямоугольников (например, географических координат) и широко применяется в геоинформационных системах (ГИС).

¶Применение

B-tree и её варианты используются в следующих областях:

• Реляционные СУБД: индексы таблиц (первичные ключи, уникальные индексы, индексы по неуникальным полям). Например, в PostgreSQL по умолчанию создаётся B-tree-индекс.
• Файловые системы: NTFS (Master File Table), ext4 (H-tree — вариант B-tree), XFS, Btrfs.
• NoSQL-базы данных: MongoDB (WiredTiger использует B+-tree), Couchbase, LevelDB (LSM-tree, но с элементами B-tree).
• Операционные системы: управление виртуальной памятью (например, в Linux — B-tree для организации page cache).
• Компиляторы и интерпретаторы: хранение символов (symbol tables) в некоторых реализациях.
• Геоинформационные системы: пространственные индексы (R-tree, UB-tree).

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

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

• Низкая высота: благодаря высокой степени ветвления B-tree имеет малую высоту даже при большом количестве записей, что минимизирует количество дисковых операций.
• Сбалансированность: все операции (поиск, вставка, удаление) выполняются за O(log n) в худшем случае.
• Эффективность для последовательного доступа: B+-tree с linked list листьев обеспечивает быстрый обход данных в порядке возрастания ключей.
• Адаптация к размеру блока: структура естественным образом вписывается в страничную организацию памяти.

¶Недостатки

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

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

• В 1979 году Дуглас Комер подсчитал, что для B-tree с t=100 и n=10^9 высота дерева не превышает 4, что делает поиск практически мгновенным даже на медленных дисках.
• Название «B-tree» не является аббревиатурой; авторы признавались, что выбрали букву «B» без специального значения, но позже возникли многочисленные интерпретации.
• В 1980-х годах B-tree была запатентована в США, но патент не был признан в Европе, что способствовало её широкому распространению в открытом ПО.
• B+-tree используется в ядре Linux для организации файловой системы Btrfs (B-tree file system).

¶Источники

• 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.
• Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). Алгоритмы: построение и анализ (3-е изд.). Вильямс.
• Hellerstein, J. M., & Stonebraker, M. (2005). Readings in Database Systems (4th ed.). MIT Press.