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

B-tree индекс: структура и механизм

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

Основные характеристики B-tree

1. Сбалансированность — все листья находятся на одинаковом уровне, что гарантирует логарифмическую сложность поиска O(log n)
2. Степень (order) — каждый узел может содержать до m потомков и m-1 ключей
3. Многоуровневость — структурирована иерархически, что минимизирует количество обращений к диску
4. Опсеченность — каждый узел может быть неполностью заполнен, но должен содержать минимальное количество элементов

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

Узел B-tree содержит:
┌─────────────────────────────────────────┐
│ K1 | K2 | K3 | ... | Km-1               │  Ключи
├─────────────────────────────────────────┤
│ P0 | P1 | P2 | P3 | ... | Pm            │  Указатели на потомков
└─────────────────────────────────────────┘

где:
- K1 < K2 < K3 < ... < Km-1
- P0 ведёт к узлам с ключами < K1
- P1 ведёт к узлам с ключами между K1 и K2
- Pm ведёт к узлам с ключами > Km-1

Пример B-tree порядка 3 (m=3)

                    [25, 50]
                   /    |    \
              /         |         \
          [10, 15]   [30, 40]   [60, 70]
         /  |  \      /  |  \    /  |  \
        5  12  20   35  45  55  65  75  80

Операции в B-tree

Поиск элемента:

def search_btree(node, key):
    """
    Поиск ключа в B-tree с начала с корня.
    Временная сложность: O(log n)
    """
    i = 0
    
    # Найти первый ключ, который >= искомому
    while i < len(node.keys) and key > node.keys[i]:
        i += 1
    
    # Если найден точный ключ
    if i < len(node.keys) and key == node.keys[i]:
        return node  # Найдено!
    
    # Если это лист, ключа нет
    if node.is_leaf:
        return None
    
    # Рекурсивный поиск в потомке
    return search_btree(node.children[i], key)

Вставка элемента:

def insert_btree(tree, key):
    """
    Вставка нового ключа в B-tree.
    При переполнении узел расщепляется.
    """
    root = tree.root
    
    # Если корень полный, создаём новый корень и расщепляем
    if is_full(root):
        new_root = Node()
        new_root.is_leaf = False
        new_root.children.append(root)
        split_child(new_root, 0)
        tree.root = new_root
    
    insert_non_full(tree.root, key)


def insert_non_full(node, key):
    """Вставка в неполный узел."""
    i = len(node.keys) - 1
    
    if node.is_leaf:
        # Простая вставка в лист
        node.keys.append(None)
        while i >= 0 and key < node.keys[i]:
            node.keys[i + 1] = node.keys[i]
            i -= 1
        node.keys[i + 1] = key
    else:
        # Найти потомка для вставки
        while i >= 0 and key < node.keys[i]:
            i -= 1
        i += 1
        
        # Расщепить потомка если нужно
        if is_full(node.children[i]):
            split_child(node, i)
            if key > node.keys[i]:
                i += 1
        
        insert_non_full(node.children[i], key)

Удаление элемента:

def delete_btree(node, key):
    """
    Удаление ключа из B-tree.
    Более сложная операция, требует балансировки.
    """
    if node.is_leaf:
        # Простое удаление из листа
        node.keys.remove(key)
    else:
        # Удаление из внутреннего узла
        # ... сложная логика с перемещением ключей ...
        pass

Почему B-tree предпочтительны для БД?

1. Минимизация обращений к диску — узлы часто соответствуют блокам на диске, большой порядок означает меньше уровней
2. Сбалансированность — гарантированное O(log n) для всех операций
3. Эффективность дисковых операций — последовательное чтение блокирует минимум операций I/O
4. Поддержка range queries — легко получить диапазон значений благодаря сортировке

B+ tree vs B-tree

B+ tree — вариант B-tree, где:

• Все ключи хранятся в листах
• Внутренние узлы содержат только указатели
• Листья связаны в отсортированный список

B+ tree структура:
        [25, 50]
       /    |    \
    [10-20][25-40][60-75]  <- листья с данными
     |-------|-------|-----  <- связный список листьев

Примеры использования в реальных БД

• PostgreSQL — B-tree индексы по умолчанию для большинства типов данных
• MySQL/InnoDB — B+ tree для индексов
• SQLite — B-tree для всех индексов
• MongoDB — B-tree индексы для _id и других полей

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