B-дерево: почему на нём построены индексы баз данных

Коротко

Проблема, которую решает

Двоичное дерево поиска на миллионе элементов имеет высоту около 20. В оперативной памяти это мгновенно.

Но если дерево лежит на диске, каждый спуск на уровень — это отдельное чтение. Обращение к SSD занимает около 100 микросекунд, к HDD — до 10 миллисекунд. Двадцать чтений превращаются в 2 миллисекунды на SSD и 200 миллисекунд на HDD.

Ключевое наблюдение: диск читает не байт, а блок — обычно 4 или 8 килобайт. Прочитать 8 килобайт стоит столько же, сколько 8 байт.

Отсюда идея B-дерева: сделать узел размером с дисковый блок и положить в него сотни ключей. Тогда высота дерева резко падает.

двоичное дерево, 10⁶ элементов:  высота ≈ 20 → 20 чтений
B-дерево с t=100:                высота = 3  → 3 чтения

Разница в семь раз по количеству обращений к диску — это и есть причина, по которой все реляционные СУБД используют B-деревья.

Устройство

Узел B-дерева порядка t содержит:

• от t−1 до 2t−1 ключей (корень может иметь меньше);
• на один указатель больше, чем ключей.

        [ 10 | 20 | 30 ]
        /    |    |    \
   [<10]  [10-20] [20-30] [>30]

Ключи внутри узла отсортированы, а указатели ведут в поддеревья со значениями из соответствующих диапазонов.

Три правила, которые поддерживаются всегда:

1. Все листья находятся на одном уровне — дерево идеально сбалансировано по высоте.
2. Каждый узел кроме корня заполнен минимум наполовину.
3. Ключи в узле отсортированы.

Второе правило — гарантия, что дерево не выродится: даже в худшем случае высота остаётся логарифмической.

Поиск

Внутри узла ищем нужный интервал (линейно или бинарным поиском), спускаемся по соответствующему указателю.

class BTreeNode:
    def __init__(self, leaf: bool = False):
        self.keys: list = []
        self.children: list = []
        self.leaf = leaf


def search(node: BTreeNode, key):
    i = 0
    # находим первый ключ, не меньший искомого
    while i < len(node.keys) and key > node.keys[i]:
        i += 1

    if i < len(node.keys) and node.keys[i] == key:
        return node, i          # нашли

    if node.leaf:
        return None             # дальше идти некуда

    return search(node.children[i], key)

Внутри узла поиск идёт в памяти и стоит копейки. Дорогая часть — переход к ребёнку, то есть чтение блока.

Вставка: разделение переполненного узла

Классические деревья при вставке делают повороты. B-дерево вместо этого разделяет переполненный узел.

Когда в узле оказывается 2t ключей:

1. средний ключ поднимается к родителю;
2. остальные делятся на два узла по t−1 ключей.

переполнение:  [ 5 | 10 | 15 | 20 | 25 ]

              ↓ поднимаем 15

родитель:            [ 15 ]
                     /     \
              [5|10]        [20|25]

Если родитель тоже переполнился, разделение поднимается выше. Дойдя до корня, оно создаёт новый корень — и это единственный способ, которым B-дерево растёт в высоту. Поэтому все листья всегда остаются на одном уровне.

Удаление и слияние

Обратная операция: если после удаления в узле осталось меньше t−1 ключей, он либо занимает ключ у соседа, либо сливается с ним. Слияние может опустошить родителя и подняться выше — вплоть до уменьшения высоты дерева.

Удаление в B-дереве — самая громоздкая часть реализации, с несколькими случаями. В боевом коде её берут из готовых библиотек.

B-дерево или B+ дерево

Реальные СУБД используют не классическое B-дерево, а его модификацию — B+ дерево. Отличия принципиальные.

Два следствия, из-за которых выбирают B+.

Больше ключей в узле. Внутренние узлы не хранят данные, только ключи и указатели, — значит в тот же блок помещается больше ключей, и дерево становится ещё ниже.

Диапазонные запросы за один проход. Листья связаны в отсортированный список, поэтому запрос WHERE age BETWEEN 20 AND 30 находит начало за O(log n) и дальше просто идёт по списку, не возвращаясь к корню.

Именно поэтому индекс в PostgreSQL, MySQL или SQLite отлично отрабатывает BETWEEN и ORDER BY.

Что из этого следует для работы с БД

Понимание B+ дерева объясняет несколько практических вещей.

Почему индекс ускоряет WHERE и ORDER BY, но не LIKE '%текст'. Дерево отсортировано по началу значения; поиск по суффиксу требует полного перебора.

Почему составной индекс работает слева направо. Индекс по (city, age) помогает запросу по city и по city + age, но не по одному age — сортировка идёт сначала по первому полю.

Почему много индексов замедляют запись. Каждая вставка обновляет все деревья, при этом возможны разделения узлов.

Почему UUID-ключи хуже автоинкремента. Последовательные ключи всегда добавляются в правый край дерева, а случайные вызывают разделения по всей структуре и фрагментацию страниц.

Где ещё применяется

Файловые системы. NTFS, ext4, Btrfs (название прямо об этом), APFS, ZFS — все хранят метаданные в B-деревьях.

Ключ-значение хранилища. BerkeleyDB, LMDB.

Индексы полнотекстового поиска.

Альтернатива для нагрузок с преобладанием записи — LSM-деревья (RocksDB, Cassandra, ClickHouse). Они пишут быстрее за счёт последовательной записи, но читают медленнее. Выбор между B-tree и LSM — одно из главных архитектурных решений при разработке хранилища.

Частые ошибки в понимании

«B» означает «binary». Нет. Точное значение автор не раскрывал; варианты — balanced, broad, Bayer (по фамилии создателя). Двоичным B-дерево точно не является.

Путаница B-дерева и B+ дерева. На собеседовании по базам данных стоит уточнять, о чём речь: индексы почти всегда B+.

Ожидание O(1) от индекса. Индекс даёт логарифм, а не константу. Хеш-индекс даёт O(1), но не поддерживает диапазоны и сортировку — поэтому по умолчанию используется B+.

Что запомнить

• B-дерево делает узел размером с дисковый блок и кладёт в него сотни ключей.
• Высота падает до 3–4 уровней даже на миллионах записей — это минимум обращений к диску.
• Растёт только через разделение корня, поэтому все листья всегда на одном уровне.
• В базах данных используется B+ дерево: данные только в листьях, листья связаны в список.
• Отсюда работают диапазонные запросы и правило «составной индекс читается слева направо».

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→