Какое дерево лежит в основе древовидных индексов?

B-дерево — основа древовидных индексов

В основе древовидных индексов в базах данных (особенно в системах как PostgreSQL, MySQL, SQLite) лежит B-дерево (B-tree) и его вариации, прежде всего B+ дерево. Это сбалансированное дерево поиска, специально разработанное для эффективной работы с дисковыми блоками большого объёма данных.

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

B-дерево оптимально для работы с дисковой памятью благодаря следующим свойствам:

• Минимизация дисковых операций — каждый узел содержит много ключей и указателей, что позволяет хранить тысячи элементов в одном блоке диска
• Гарантированная сбалансированность — все листья находятся на одном уровне, обеспечивая логарифмическую сложность O(log n)
• Эффективный обход диапазонов — особенно в вариации B+ дерева, где листья связаны в список
• Минимум ребалансировок — структура требует редких операций переустройства при вставке/удалении

Структура B-дерева

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

class BTreeNode:
    def __init__(self, t, leaf=False):
        self.keys = []  # Ключи (значения для поиска)
        self.children = []  # Указатели на дочерние узлы
        self.leaf = leaf  # True если листовой узел
        self.t = t  # Минимальная степень (параметр дерева)

• Каждый узел (кроме корня) содержит от t-1 до 2t-1 ключей
• Внутренний узел содержит на один указатель больше, чем ключей
• Все листья находятся на одной глубине

B+ дерево — оптимизация для БД

B+ дерево — это более специализированная вариация для систем хранения:

• Все данные хранятся только в листьях (внутренние узлы содержат только ключи навигации)
• Листья связаны в двусвязный список для быстрого обхода диапазонов
• Внутренние узлы — чистая структура навигации
• Обеспечивает ещё более эффективный доступ к последовательным данным

Пример использования в Python

from btrees.OOBTree import OOBTree

# B-дерево из модуля btrees
btree = OOBTree()
btree[5] = "Five"
btree[3] = "Three"
btree[7] = "Seven"

# Операции O(log n)
print(btree[5])  # O(log n)
print(list(btree.items(3, 7)))  # Эффективный диапазонный поиск

В контексте баз данных

В PostgreSQL, MySQL индексы создаются как B-деревья:

# SQL создаёт индекс B-дерева
CREATE INDEX idx_user_email ON users(email);

# В СУБД индекс организован как B+ дерево
# Поиск: O(log n)
# Диапазонный запрос: O(log n + k) где k - число результатов

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