B-Tree: Деревья для дисков и баз данных

Цели урока

• Понять почему BST не подходит для дисков
• Изучить структуру B-Tree: много ключей в узле
• Освоить поиск и вставку с разделением
• Узнать разницу между B-Tree и B+ Tree

Предварительные знания

• Деревья
• BST
• Понимание I/O

• Введение в деревья

Каждый раз, когда вы делаете SELECT в базе данных, B+ Tree находит нужную строку среди миллиардов за миллисекунды. Без этой структуры Google, Amazon, и ваш банк не смогли бы работать.

• MySQL/PostgreSQL - все индексы на B+ Tree
• MongoDB - индексы для NoSQL
• Файловые системы (NTFS, ext4) - организация метаданных
• SQLite - встроенная БД в каждом смартфоне

Байер, Маккрейт и структура за каждой базой данных

B-Tree изобрели Рудольф Байер и Эдвард Маккрейт в исследовательской лаборатории Boeing около 1970 года и описали в статье 1972 года «Organization and Maintenance of Large Ordered Indices». Они решали конкретную инженерную задачу: как поддерживать большой отсортированный индекс на медленном дисковом хранилище, сохраняя при этом эффективными и поиск, и обновления. Их ответом было расширить каждый узел так, чтобы он хранил много ключей и много детей, сопоставив узел дисковой странице, чтобы одно чтение страницы приносило сразу сотни ключей. Дерево остаётся сбалансированным за счёт разделения переполненных узлов и проталкивания среднего ключа вверх, а все листья держатся на одной глубине. Вариант B+ Tree, который хранит данные только в связанных листьях, стал стандартом для range-запросов и сегодня лежит в основе индексов PostgreSQL и MySQL InnoDB, а также файловых систем вроде NTFS, ext4 и HFS+.

Почему не BST для баз данных?

**Проблема:** BST отлично работает в памяти, но база данных хранит терабайты на диске.

**Решение:** минимизировать количество обращений к диску. B-Tree хранит много ключей в одном узле → меньше уровней → меньше I/O.

Структура B-Tree

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

**Размер узла ≈ размер страницы диска (4KB).** Один узел = одно чтение с диска, но в нём сотни ключей!

Свойства B-Tree

**B-Tree порядка m** (m = максимум детей):

1. Каждый узел имеет **максимум m детей**
2. Каждый внутренний узел (кроме корня) имеет **минимум ⌈m/2⌉ детей**
3. Корень имеет **минимум 2 детей** (если не лист)
4. Все **листья на одном уровне**
5. Узел с k детьми содержит **k-1 ключей**

**Высота B-Tree с N ключами: O(log_m N)** - логарифм по основанию m. При m=1000, миллиард ключей = 3-4 уровня!

Поиск в B-Tree

Поиск похож на BST, но в каждом узле ищем среди нескольких ключей.

**Сложность:** O(log_m N) обращений к диску × O(m) сравнений в узле. На практике бинарный поиск внутри узла: O(log m).

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

Вставка всегда в лист. Если лист переполнен - **разделяем (split)** его на два.

Split может каскадироваться вверх! Если родитель тоже полон, он тоже разделяется. В худшем случае - до корня.

B+ Tree: Вариация для баз данных

**B+ Tree** - вариант B-Tree, где все данные только в листьях, а внутренние узлы - только для навигации.

**MySQL InnoDB, PostgreSQL, SQLite, MongoDB** - все используют B+ Tree для индексов. Это фундамент современных СУБД.

B-Tree и B+ Tree

• B-Tree: много ключей в узле → мало уровней → мало I/O
• Высота O(log_m N), при m=1000 очень плоские
• Split при переполнении поддерживает баланс
• B+ Tree: данные только в листьях + связный список
• Фундамент всех современных СУБД

Экосистема баз данных

B+ Tree - для точного поиска. Для приблизительных проверок (есть ли элемент?) используют вероятностные структуры вроде Bloom Filter.

• Bloom Filter — Вероятностная структура

Связанные уроки

• ds-11-bst — B-дерево обобщает BST на множество ключей в узле
• ds-12-balanced-trees — Расширяет сбалансированные деревья высоким ветвлением для диска
• ds-22-skip-list — Обе хранят упорядоченные данные с поиском за O(log n)
• db-09-indexes-btree — Индексы B-tree в БД - это данная структура на практике
• os-09-filesystems — Файловые системы используют B-деревья для индексации блоков на диске