Я построил B-дерево на Python и понял, почему Postgres использует его для индексов

Почему B-дерево, а не бинарное дерево?

Большинство из нас учили бинарные деревья поиска в школе. Каждый узел хранит одно значение. Левый потомок меньше, правый — больше. Поиск — O(log n). Всё чисто. Но базы данных ненавидят бинарные деревья. Вот почему.

Бинарное дерево с 1 миллионом узлов имеет высоту около 20. Это значит 20 чтений с диска, чтобы найти одну строку. Каждое чтение — примерно 1 мс на HDD (или 100 микросекунд на SSD). Это быстро накапливается.

B-деревья решают эту проблему, будучи «широкими, а не высокими». Каждый узел хранит несколько ключей и имеет несколько потомков. B-дерево порядка 100 (100 ключей на узел) с 1 миллионом записей имеет высоту всего 3. Три чтения с диска. Именно поэтому Postgres использует его.

Правило: каждый внутренний узел хранит от t-1 до 2t-1 ключей, где t — минимальная степень. Листовые узлы имеют те же ограничения. Это автоматически поддерживает дерево сбалансированным.

Структура данных

class BTreeNode:
    def __init__(self, leaf=False):
        self.keys = []          # отсортированный список ключей
        self.children = []      # ссылки на дочерние узлы (пусто для листьев)
        self.leaf = leaf
        self.values = {}        # отображение ключ -> значение (для листьев)

class BTree:
    def __init__(self, t=3):
        self.root = BTreeNode(leaf=True)
        self.t = t              # минимальная степень

Минимальная степень t контролирует ширину дерева. При t=3 каждый узел хранит от 2 до 5 ключей. При t=100 (как Postgres использует внутри) каждый узел хранит от 99 до 199 ключей. Больше t — короче дерево. Короче дерево — меньше чтений с диска.

Поиск

Поиск — самая простая операция. Спускаемся по дереву, на каждом узле выполняем бинарный поиск по ключам, идём влево или вправо в зависимости от того, куда попадает искомый ключ.

def search(self, node, key):
    # находим первый ключ, больший или равный искомому
    i = 0
    while i < len(node.keys) and key > node.keys[i]:
        i += 1
    # точное совпадение
    if i < len(node.keys) and key == node.keys[i]:
        if node.leaf:
            return node.values.get(key)
        # внутренние узлы не хранят значения в реальной БД
        # они просто направляют поиск
        return self.search(node.children[i+1], key)
    # не найдено на этом узле, идём в подходящего потомка
    if node.leaf:
        return None  # ключ не существует
    return self.search(node.children[i], key)

def get(self, key):
    return self.search(self.root, key)

Обратите внимание на логику: на каждом узле мы сканируем список ключей, чтобы найти, куда вставляется наш ключ, затем либо возвращаем значение (если найдено в листе), либо рекурсивно спускаемся в нужного потомка. Высота — O(log_t n), поэтому количество рекурсивных вызовов крошечное даже для миллионов строк.

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

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

Операция split берёт полный дочерний узел, разрезает его пополам и поднимает медианный ключ в родительский. Вот почему B-деревья остаются сбалансированными без какой-либо логики вращения (в отличие от AVL или красно-чёрных деревьев).

def split_child(self, parent, i):
    """
    Разделить parent.children[i] и поднять медианный ключ в parent.
    """
    t = self.t
    full_child = parent.children[i]
    new_child = BTreeNode(leaf=full_child.leaf)
    
    # индекс медианного ключа
    mid = t - 1
    
    # поднимаем медианный ключ в родителя
    parent.keys.insert(i, full_child.keys[mid])
    parent.children.insert(i+1, new_child)
    
    # правая половина уходит в new_child
    new_child.keys = full_child.keys[mid+1:]
    full_child.keys = full_child.keys[:mid]
    
    # разделяем указатели на потомков, если внутренний узел
    if not full_child.leaf:
        new_child.children = full_child.children[t:]
        full_child.children = full_child.children[:t]
    
    # разделяем значения, если лист
    if full_child.leaf:
        for k in new_child.keys:
            new_child.values[k] = full_child.values.pop(k)

Теперь вставка использует подход сверху вниз. Когда мы спускаемся к месту вставки, мы разделяем любой полный узел, который встречаем. Это гарантирует, что когда мы достигнем листа, в нём всегда будет место.

def insert_non_full(self, node, key, value):
    i = len(node.keys) - 1
    if node.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
        node.values[key] = value
    else:
        # ищем потомка для рекурсии
        while i >= 0 and key < node.keys[i]:
            i -= 1
        i += 1
        # разделяем потомка, если он полон
        if len(node.children[i].keys) == 2 * self.t - 1:
            self.split_child(node, i)
            if key > node.keys[i]:
                i += 1
        self.insert_non_full(node.children[i], key, value)

def insert(self, key, value):
    root = self.root
    if len(root.keys) == 2 * self.t - 1:
        # корень полон, нужно увеличить дерево
        new_root = BTreeNode(leaf=False)
        new_root.children.append(self.root)
        self.split_child(new_root, 0)
        self.root = new_root
        self.insert_non_full(new_root, key, value)
    else:
        self.insert_non_full(root, key, value)

Разделение корня — единственный случай, когда высота дерева увеличивается. Этот единственный путь роста гарантирует, что B-дерево всегда идеально сбалансировано.

Диапазонные запросы

Базы данных используют B-деревья и для диапазонных запросов. WHERE created_at BETWEEN '2024-01-01' AND '2024-03-31' — это диапазонное сканирование B-дерева.

def range_query(self, node, low, high, results):
    """
    Собрать все пары ключ-значение, где low <= key <= high.
    """
    i = 0
    while i < len(node.keys) and node.keys[i] < low:
        i += 1
    while i < len(node.keys) and node.keys[i] <= high:
        if node.leaf:
            results.append((node.keys[i], node.values[node.keys[i]]))
        else:
            # сначала рекурсия в левого потомка
            self.range_query(node.children[i], low, high, results)
            if node.keys[i] <= high:
                results.append((node.keys[i], node.keys[i]))  # внутренний ключ
        i += 1
    # рекурсия в крайнего правого релевантного потомка
    if not node.leaf and i < len(node.children):
        self.range_query(node.children[i], low, high, results)

def get_range(self, low, high):
    results = []
    self.range_query(self.root, low, high, results)
    return sorted(results)

Обратите внимание: мы полностью пропускаем поддеревья, диапазон ключей которых не пересекается с нашим запросом. Это то самое поведение «index skip scan», которое вы видите в выводе EXPLAIN ANALYZE.

Собираем всё вместе: быстрая демонстрация

bt = BTree(t=3)

# вставляем ID пользователей с именами
for uid, name in [
    (1, "alice"),
    (5, "bob"),
    (10, "carol"),
    (3, "dave"),
    (7, "eve"),
    (12, "frank"),
    (2, "grace"),
    (8, "heidi"),
    (15, "ivan"),
    (4, "judy"),
    (6, "kate"),
    (11, "leo"),
]:
    bt.insert(uid, name)

# точечный поиск
print(bt.get(7))  # eve

# диапазонный запрос
print(bt.get_range(3, 10))
# [(3, 'dave'), (4, 'judy'), (5, 'bob'), (6, 'kate'),
#  (7, 'eve'), (8, 'heidi'), (10, 'carol')]

Обе операции быстры независимо от общего размера, потому что высота дерева остаётся низкой.

Что это мне дало в понимании реального поведения Postgres

Как только я понял структуру, несколько вещей встали на свои места.

Раздувание B-дерева (B-tree bloat) происходит, когда множество удалений оставляют полупустые страницы. Postgres помечает такие страницы как «мёртвые», но не сразу переиспользует их. Дерево становится выше, а страницы фрагментируются. VACUUM и REINDEX уплотняют эти страницы. Тот самый инцидент в 2 часа ночи теперь стал полностью понятен.

Почему у составных индексов есть правила порядка столбцов. Составной индекс по (city, created_at) — это B-дерево, отсортированное сначала по city, затем по created_at внутри каждого city. Запрос WHERE city = 'Nairobi' может использовать индекс. Запрос WHERE created_at > '2024-01-01' без фильтра по city — нет, потому что дерево не отсортировано по created_at на корневом уровне.

Почему LIKE 'nairobi%' использует индекс, а LIKE '%nairobi' — нет. Поиск по префиксу совпадает с сортировкой B-дерева. Поиск по суффиксу потребовал бы сканирования всех листьев.

Настройка fill factor. Postgres позволяет задать fill factor для индекса (по умолчанию 90%). Это оставляет 10% каждой страницы пустыми при начальном построении, резервируя место для вставок. Если ваша таблица получает много вставок, меньший fill factor уменьшает количество разделений. Если она в основном read-only, оставьте 90%.

Соберите игрушечную версию того, что индексируете

До этого упражнения я относился к индексам Postgres как к чёрному ящику. Указать правильные столбцы, проверить EXPLAIN, идти дальше.

Теперь я понимаю, почему порядок столбцов в составном индексе важен, почему VACUUM влияет на производительность запросов, и почему B-дерево побеждает хеш-индекс в диапазонных запросах, но проигрывает в поиске только по равенству.

Игрушка не заменила знание Postgres. Она заставила всё остальное становиться понятным быстрее.

В следующий раз, когда ваш EXPLAIN покажет сканирование индекса, которое вы не понимаете, спросите себя: что делает B-дерево на этом шаге? Ответ обычно — «пропускает поддеревья, которые не нужны». В этом весь трюк.

Практический вывод: прямо сейчас откройте свою базу данных, найдите запрос с медленным index scan и попробуйте представить, как B-дерево перемещается по узлам. Если вы не уверены — постройте игрушечную реализацию, как я. Это окупается.