B-tree индекс

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

История

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

Основные свойства и устройство

B-tree индекс строится на основе одноимённой структуры данных, которая обладает рядом строгих свойств, гарантирующих её сбалансированность и предсказуемую производительность.

Определение и параметры

B-tree порядка m (или степени t) — это дерево, удовлетворяющее следующим условиям:

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

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

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

Массив ключей (например, [3, 7, 15]).
Массив указателей на дочерние узлы (для внутренних узлов). Количество указателей на единицу больше количества ключей.
Флаг, является ли узел листом.
В СУБД каждый ключ может быть связан с идентификатором записи (RID — row identifier) или указателем на строку данных.

Высота дерева и производительность

Высота B-tree растёт логарифмически от количества ключей, но основание логарифма равно степени ветвления (которое может быть большим, например, 100 или 1000). Для дерева порядка t, содержащего N ключей, максимальная высота h составляет:

h <= log_t((N+1)/2)

На практике, для миллиарда записей при t = 100 высота дерева составит всего 4–5 уровней. Это означает, что для поиска любого ключа необходимо прочитать с диска не более 5 узлов, что является ключевым преимуществом B-tree перед бинарными деревьями поиска (BST), высота которых в худшем случае может быть равна N.

Операции над B-tree индексом

Поиск

Алгоритм поиска ключа K:

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

Вставка

Вставка нового ключа всегда начинается с листа:

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

Средний ключ перемещается в родительский узел.
Узел делится на два узла, каждый примерно по t-1 ключей.
Если родительский узел также переполнен, процесс разделения рекурсивно поднимается вверх. В худшем случае разделение может дойти до корня, что увеличит высоту дерева на 1.

Удаление

Удаление ключа — самая сложная операция, требующая поддержания сбалансированности:

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

Заимствование (rotation): если соседний узел (брат) имеет больше t-1 ключей, один ключ перемещается через родительский узел.
Слияние (merge): если соседний узел также имеет t-1 ключей, узлы сливаются в один, а ключ из родителя опускается вниз. Это может вызвать рекурсивное уменьшение заполнения выше.

Применение в СУБД

B-tree (и его вариации, такие как B+tree) являются стандартом де-факто для построения индексов в реляционных базах данных.

B+tree — основная модификация

Наиболее распространённой реализацией в современных СУБД (PostgreSQL, MySQL, Oracle, SQL Server) является B+tree — модификация B-tree, в которой:

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

Это позволяет:

Увеличить степень ветвления внутренних узлов, так как они не содержат данных.
Выполнять эффективные запросы на диапазон (WHERE id BETWEEN 10 AND 100) — достаточно найти первый лист и пройти по цепочке листьев.

Типы индексов на основе B-tree

В СУБД B-tree индексы могут быть:

Кластеризованные (clustered): данные таблицы физически упорядочены в соответствии с индексом. Листья B+tree содержат полные строки данных. Таблица может иметь только один кластеризованный индекс (например, в Microsoft SQL Server).
Некластеризованные (non-clustered): листья содержат только ключи и указатели (RID) на строки в куче (heap) или кластеризованном индексе. Таблица может иметь множество некластеризованных индексов.
Уникальные (unique): гарантируют отсутствие дубликатов ключей.
Составные (composite): включают несколько столбцов. Порядок столбцов в индексе важен для эффективности запросов.

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

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

Высокая скорость поиска, вставки и удаления (O(log N)).
Эффективная работа с диапазонными запросами.
Сбалансированность — гарантированное время доступа независимо от порядка вставки данных.
Хорошая производительность при работе с дисковыми накопителями (минимизация количества операций ввода-вывода).

Недостатки:

Накладные расходы на поддержание сбалансированности (разделение и слияние узлов).
Для очень частых вставок может потребоваться периодическая реорганизация (rebuild) индекса.
Неэффективны для поиска по частичному совпадению (LIKE '%text%').
Занимают дополнительное дисковое пространство (обычно 10–30% от размера таблицы).

Альтернативы B-tree

В некоторых сценариях B-tree уступают другим структурам:

Hash-индексы: обеспечивают O(1) для точного поиска, но не поддерживают диапазонные запросы и сортировку. Используются в PostgreSQL, MySQL (MEMORY engine).
GiST (Generalized Search Tree): обобщённое дерево поиска, поддерживающее произвольные типы данных (геометрические, текстовые). Используется в PostgreSQL для полнотекстового поиска и геоданных.
LSM-tree (Log-Structured Merge-tree): оптимизированы для высоких нагрузок на запись (write-heavy workloads). Используются в NoSQL-системах (LevelDB, RocksDB, Cassandra, ScyllaDB). Данные сначала записываются в буфер в памяти, затем асинхронно сливаются на диск.
Bitmap-индексы: эффективны для столбцов с небольшим количеством уникальных значений (пол, статус). Используются в Oracle, PostgreSQL.

Источники

Bayer, R., & McCreight, E. (1970). «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.
Garcia-Molina, H., Ullman, J. D., & Widom, J. (2008). «Database Systems: The Complete Book» (2nd ed.). Pearson.
Документация PostgreSQL: Chapter 11. Indexes (11.3. B-Tree Indexes).
Документация MySQL: 8.3.2 Comparison of B-Tree and Hash Indexes.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →