# B-дерево

> Сбалансированное сильно ветвящееся дерево поиска, оптимизированное для хранения на диске; его вариант B+-дерево лежит в основе индексов почти всех реляционных СУБД и многих файловых систем.

Источник: https://llmdocs.ru/wiki/b-tree/ · обновлено 2026-11-09 · лицензия CC BY-SA 4.0

- **Авторы**: Рудольф Байер, Эдвард Маккрейт (Boeing)
- **Год**: 1970 (публикация — 1972)
- **Сложность поиска, вставки, удаления**: O(log n)
- **Ветвление**: сотни ключей на узел
- **Вариант в СУБД**: B+-дерево — данные только в листьях, листья связаны
- **Где используется**: PostgreSQL, MySQL InnoDB, SQLite, Oracle, файловые системы (NTFS, Btrfs, XFS, APFS)
- **Альтернатива**: LSM-дерево (RocksDB, Cassandra)
**B-дерево** — сбалансированное дерево поиска, в котором каждый узел хранит не один ключ, как в двоичном дереве, а десятки или сотни упорядоченных ключей и столько же ссылок на дочерние узлы. Благодаря большому ветвлению дерево получается очень низким: даже для миллиардов записей нужно три-четыре уровня. Структура создана для данных, хранящихся на диске, где дорого не сравнение ключей, а каждое чтение блока.

Вариант **B+-дерево** — стандартная структура [индексов](https://llmdocs.ru/wiki/database-index.md) в [PostgreSQL](https://llmdocs.ru/wiki/postgresql.md), [MySQL](https://llmdocs.ru/wiki/mysql-mariadb.md), [SQLite](https://llmdocs.ru/wiki/sqlite.md), Oracle и SQL Server, а также основа многих файловых систем.

## История

Рудольф Байер и Эдвард Маккрейт разработали B-дерево в 1970 году в исследовательской лаборатории Boeing; статья вышла в 1972 году.[1] Что означает буква «B», авторы так и не уточнили: среди версий — Boeing, Bayer, *balanced* («сбалансированное») и *broad* («широкое»). Уже к 1979 году обзор Дугласа Комера назывался «Вездесущее B-дерево» — структура стала стандартом для индексов баз данных и файлов.[2]

## Почему не двоичное дерево

Диск и SSD читают данные не байтами, а **страницами** — блоками по 4–16 КБ. Обращение к новой странице на порядки дороже сравнения в памяти. Двоичное дерево для миллиона ключей имеет глубину около 20 — это 20 случайных чтений с диска на каждый поиск. B-дерево с узлом размером в страницу и 500 ключами на узел вмещает миллион записей в три уровня, причём корень и верхний уровень почти всегда находятся в кэше. Поиск сводится к одному-двум чтениям.

| Записей | Двоичное дерево (уровней) | B-дерево, 500 ключей на узел (уровней) |
|---|---|---|
| 1 000 | 10 | 2 |
| 1 000 000 | 20 | 3 |
| 1 000 000 000 | 30 | 4 |

## Устройство

B-дерево порядка *m* удовлетворяет правилам:

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

**Поиск** начинается с корня: в узле двоичным поиском находится нужный промежуток, затем переход к соответствующему потомку, и так до листа. **Вставка** добавляет ключ в лист; если лист переполнен, он **расщепляется** пополам, а средний ключ поднимается в родителя. Расщепление может дойти до корня — тогда появляется новый корень, и дерево вырастает на уровень. Рост «снизу вверх» и сохраняет баланс. **Удаление** при недозаполнении узла занимает ключи у соседа или сливает узлы. Все операции выполняются за O(log n) (см. [Алгоритм и O-нотация](https://llmdocs.ru/wiki/big-o.md)).

## B+-дерево

В базах данных почти всегда используется вариант **B+-дерево**:

- значения (или ссылки на строки таблицы) хранятся **только в листьях**, а внутренние узлы содержат лишь ключи-разделители — поэтому они компактнее и ветвление выше;
- листья связаны в список, так что **диапазонный запрос** (`WHERE created_at BETWEEN ...`, `ORDER BY`) находит начало диапазона и затем просто идёт по листьям.

Этим объясняется, почему B-tree-индекс помогает не только равенству, но и сравнениям, сортировке и поиску по префиксу строки.

## В конкретных СУБД

- **PostgreSQL** — индекс по умолчанию — B-дерево (реализация по алгоритму Лемана — Яо с поддержкой параллельного доступа); страница 8 КБ; дедупликация одинаковых ключей с версии 13. Строки таблицы хранятся отдельно, в «куче», а индекс ссылается на них.[3]
- **MySQL InnoDB** — таблица сама хранится как B+-дерево по первичному ключу (**кластерный индекс**), страница 16 КБ; вторичные индексы ссылаются на значение первичного ключа. Поэтому случайный UUID в качестве первичного ключа приводит к частым расщеплениям страниц, а последовательные идентификаторы — нет.[5]
- **SQLite** — вся база данных — набор B-деревьев в одном файле: таблицы хранятся как B+-деревья по `rowid`, индексы — как B-деревья.[4]

## B-деревья и LSM-деревья

Для нагрузок с очень интенсивной записью используют альтернативу — **LSM-дерево** (*log-structured merge tree*): записи сначала накапливаются в памяти, затем сбрасываются на диск отсортированными файлами, которые фоном сливаются.[6]

| | B+-дерево | LSM-дерево |
|---|---|---|
| Запись | обновление на месте, случайный ввод-вывод | последовательная запись, очень быстро |
| Чтение | предсказуемо быстрое | может требовать проверки нескольких файлов |
| Фоновая работа | очистка страниц | постоянное слияние (compaction) |
| Примеры | PostgreSQL, InnoDB, SQLite | RocksDB, Cassandra, ScyllaDB, [ClickHouse](https://llmdocs.ru/wiki/clickhouse.md) (MergeTree) |

## Практические следствия

- Индексу нужна память: «горячие» верхние уровни должны помещаться в кэш СУБД.
- Порядок столбцов в составном индексе определяет, какие запросы он ускоряет, — ключи сравниваются слева направо.
- Частые вставки в середину и удаления фрагментируют страницы; периодическая перестройка (`REINDEX`) возвращает компактность.

## См. также

- [Индекс (базы данных)](https://llmdocs.ru/wiki/database-index.md)
- [Дерево и граф](https://llmdocs.ru/wiki/trees-graphs.md)
- [PostgreSQL](https://llmdocs.ru/wiki/postgresql.md)
- [SQLite](https://llmdocs.ru/wiki/sqlite.md)
- [Структуры данных](https://llmdocs.ru/wiki/data-structures.md)

## Источники

1. [R. Bayer, E. McCreight — Organization and Maintenance of Large Ordered Indexes (Acta Informatica, 1972)](https://link.springer.com/article/10.1007/BF00288683)
2. [D. Comer — The Ubiquitous B-Tree (ACM Computing Surveys, 1979)](https://dl.acm.org/doi/10.1145/356770.356776)
3. [PostgreSQL Documentation — B-Tree Indexes](https://www.postgresql.org/docs/current/btree.html)
4. [SQLite — Database File Format](https://www.sqlite.org/fileformat2.html)
5. [MySQL — Clustered and Secondary Indexes (InnoDB)](https://dev.mysql.com/doc/refman/8.4/en/innodb-index-types.html)
6. [P. O'Neil et al. — The Log-Structured Merge-Tree (LSM-Tree) (1996)](https://www.cs.umb.edu/~poneil/lsmtree.pdf)