Как устроен B-tree индекс?

Устройство B-tree индекса

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

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

B-tree индекс организован как многоуровневое сбалансированное дерево, где:

• Все листовые узлы находятся на одном уровне — это гарантирует, что поиск любого элемента требует одинакового количества шагов.
• Каждый узел (кроме корневого) содержит от m/2 до m ключей и указателей, где m — порядок дерева.
• Ключи в узле отсортированы, что позволяет использовать бинарный поиск внутри узла.

Структура узла B-tree

Каждый узел B-tree содержит:

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

-- Пример создания B-tree индекса в PostgreSQL
CREATE INDEX idx_users_email ON users(email);

Как работает поиск по B-tree

Процесс поиска значения в B-tree индексе происходит сверху вниз:

1. Начинаем с корневого узла. В нем выполняется бинарный поиск нужного ключа.
2. Переходим по указателю. Если ключ не найден точно, выбираем указатель между двумя ключами, в диапазоне которых находится искомое значение.
3. Повторяем процесс на следующем уровне, пока не достигнем листового узла.
4. В листовом узле находится либо непосредственно искомая запись (в heap-organized таблицах), либо указатель на нее (в clustered индексах).

// Упрощенная иллюстрация поиска в B-tree (псевдокод)
func BTreeSearch(node Node, key Key) *Record {
    for !node.IsLeaf() {
        // Бинарный поиск в ключах узла
        index := binarySearch(node.Keys, key)
        node = node.Children[index] // Переход к дочернему узлу
    }
    // Поиск в листовом узле
    index := binarySearch(node.Keys, key)
    if node.Keys[index] == key {
        return node.Records[index]
    }
    return nil // Ключ не найден
}

Ключевые операции и их сложность

• Поиск (O(log n)) — как описано выше, благодаря сбалансированности дерева.
• Вставка (O(log n)):

    *   Находим листовой узел для вставки.
    *   Если узел переполнен (ключей > `m-1`), выполняется **расщепление узла** — он делится на два, а средний ключ поднимается в родительский узел.
    *   Расщепление может подниматься вплоть до корня, увеличивая высоту дерева.

• Удаление (O(log n)):

    *   Более сложная операция, может потребовать **слияния узлов** или **перераспределения ключей** между соседними узлами для поддержания баланса.

Почему B-tree, а не другие структуры?

• Против красно-черных деревьев: B-tree лучше для диска, т.к. один узел (страница) содержит много ключей, что уменьшает высоту дерева и количество I/O операций.
• Против хэш-индексов: B-tree поддерживает диапазонные запросы (BETWEEN, >, <, LIKE 'prefix%') и сортировку, что недоступно хеш-индексам.
• Против bitmap индексов: B-tree эффективен при высокой кардинальности данных и частых обновлениях.

B+tree — эволюция для баз данных

На практике современные СУБД (PostgreSQL, MySQL InnoDB, Oracle) используют B+tree — улучшенную версию B-tree, где:

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

Особенности реализации в различных СУБД

• PostgreSQL: B-tree индексы поддерживают NULL, уникальность, составные индексы, покрывающие индексы (с PostgreSQL 11+).
• MySQL InnoDB: Использует B+tree для кластерных индексов (первичный ключ = данные таблицы) и вторичных индексов.
• Oracle: B-tree индексы могут быть сжатыми (key compression) для экономии места.

Достоинства и недостатки

Достоинства:

• Предсказуемая производительность O(log n).
• Поддержка точного поиска, диапазонных запросов и сортировки.
• Эффективность при частых обновлениях (по сравнению с bitmap).
• Автоматическое поддержание баланса.

Недостатки:

• Не самый компактный вид индекса.
• Может деградировать при частых вставках/удалениях (требуется перестроение).
• Не оптимален для запросов с префиксом %suffix (нужны полнотекстовые индексы).

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