Когда впервые изучаешь внутренности СУБД, кажется, что магия кроется в оптимизаторе запросов, буферном пуле, SSD или хитрых алгоритмах MVCC. Но стоит открыть любой учебник или системный код MySQL, PostgreSQL, SQLite — и внезапно оказывается, что главный герой дисковой производительности… структура из 1972 года.
B-Tree — тот самый незаметный стержень, благодаря которому ваши SELECT’ы приходят за миллисекунды, а не за секунды.
И, что удивительно, альтернативы всё ещё не смогли вытеснить B-Tree из триллионов запросов в день.
Почему? Давайте разберёмся глубже, чем обычно.
🧩 Дисковая реальность, которую программисты любят недооценивать
В оперативной памяти всё быстро, красиво и детерминировано. BST? AVL? Красно-чёрные деревья? Всё это звучит великолепно… пока данные лежат в RAM.
Но стоит переместить структуру на диск — и всё ломается.
CPU выполняет 100+ млн операций в секунду, а диск — это всё ещё гигантское ведро гравия:
- 📀 HDD: 10–15 мс на поиск (seek)
- ⚡ SSD: 0.05–0.3 мс на операция ввода/вывод (I/O)
- 🧠 RAM: 0.0001 мс на доступ
Разница между RAM и диском достигает 100 000×.
И это фундаментальная причина, по которой обычные бинарные деревья обречены: каждый переход к дочернему узлу — это отдельный поиск.
Для 1 млрд элементов BST потребует глубину ≈ 30.
30 дисковых операций → до 300 мс на HDD.
Это не база данных — это археология.
🌲 И тут на сцену выходит B-Tree: не дерево, а небоскрёб
Вместо того чтобы думать «вглубь», B-Tree думает «вширь».
Это архитектура эпохи дисков: если уж всё равно читаем целый блок (4–16 KB), почему бы не запихнуть в него сотню или тысячу ключей?
Так появляются узлы с 100–1000 детьми.
Высота дерева падает почти магически:
- 🌿 Разветвление (Fanout) 100 → высота = 3 для 1 млн строк, 5 для 1 млрд
- 🌳 Разветвление 1000 → высота = 2 и 3 соответственно
То есть база может найти нужную строку, сделав:
🔎 всего 2–5 чтений с диска.
А теперь сравните с тем, что делают BST или Red-Black Tree — 20–30 чтений.
Шансов нет.
🧠 Почему все СУБД выбирают B+-Tree, а не обычный B-Tree
Забавный факт: почти все современные базы используют B+-Tree, хотя называют его B-Tree.
Разница простая:
- 🌿 Внутренние узлы содержат только ключи, помогающие навигации
- 🌱 Листья содержат полные данные (или ссылки на них)
- 🔗 Листья связаны двусвязным списком — бесплатно получаем быстрые диапазоны
Это превращает B+-Tree в идеальный индекс:
- быстрый поиск
- последовательный перебор
- логичные операции расщепления и слияния (split/merge)
- все листья на одном уровне
Неудивительно, что его используют MySQL InnoDB, PostgreSQL, SQLite, SQL Server, Oracle, MongoDB WiredTiger — буквально весь рынок.
⚙️ Как B-Tree делают ваш SELECT мгновенным
Поиск — это простое путешествие сверху вниз:
- 🌰 узел 1: бинарный поиск по ключам → выбираем нужного ребёнка
- 🌰 узел 2: снова бинарный поиск → спускаемся ниже
- 🌰 лист: нашли значение
Получается:
⭐ log₍fanout₎(n) переходов между уровнями
⭐ log₂(fanout) сравнений внутри узла
При fanout=1000 для 1 млрд записей:
➡️ высота ≈ 3
➡️ 3 I/O → < 1 мс на SSD
Секрет — в том, что узлы идеально подогнаны под размер дискового блока.
🧨 Тёмная сторона B-Tree: слабые места, о которых говорят редко
Несмотря на эффективность, B-Tree далеки от идеала. И это важно знать, особенно если вы проектируете высоконагруженные системы.
✒️ Писать в B-Tree трудно
Каждый insert может вызвать цепочку событий:
- ✂️ разделение (split) листа
- ✂️ разделение родителя
- ✂️ разделение дедушки
- ⬆️ увеличение высоты
Это порождает:
🔥 усиление записи (write-amplification)
🔥 до нескольких записей на одну логическую вставку (insert)
Поэтому в системах с высокой нагрузкой на запись побеждают LSM-Tree (Cassandra, RocksDB, LevelDB).
🧩 Многоколоночные диапазоны — слабое место
B-Tree прекрасно обрабатывает:
➡️ диапазон по первому столбцу индекса
Но если запрос:
WHERE date > ... AND amount > ...
то B-Tree использует только первую колонку, а вторую придётся фильтровать вручную.
Поэтому для аналитики используют:
- 🔷 BRIN
- 🔷 GiST
- 🔷 GIN
- 🔷 R-Tree
- 🔷 columnar storage
📦 Фрагментация и пустоты в узлах
После тысяч вставок/удалений дерево разрыхляется:
- листья частично пустые
- увеличивается высота
- растёт размер индекса
PostgreSQL решает это VACUUM'ом, MySQL — OPTIMIZE TABLE.
🧬 Почему B-Tree переживает все архитектуры от HDD до SSD
На самом деле B-Tree — это не алгоритм, а философия:
«Максимально используй каждый дисковый блок.»
SSD быстрее, но принцип не изменился:
минимум I/O → максимум скорости.
LSM-Tree популярны, но это про записи, а не про чтения.
Hash-индексы быстры, но не поддерживают диапазоны.
Колонарка великолепна, но только для OLAP.
Для классического OLTP, поиска по ключу и диапазонных запросов нет ничего надёжнее B-Tree.
🧠 Мой личный взгляд
B-Tree — это архитектура, созданная специально под ограничения железа.
Её «вечность» объясняется просто: она идеально ложится на любой хранилище, который читает данные блоками.
Да, LSM-Tree и columnar форматы решают другие задачи, но B-Tree остаётся швейцарским ножом реляционных СУБД — достаточно быстрый, достаточно компактный и идеально сбалансированный.
Мы сменили HDD на SSD, добавили NVMe, увеличили память в сотни раз… а B-Tree даже не пришлось «оптимизировать под новое поколение».
Он уже был оптимальным.
И в этом есть своя инженерная красота:
алгоритм, который выигрывает не скоростью, а пониманием физики хранения.
🔗 Источники и ссылки
Оригинальная новость:
B-Trees: Why Every Database Uses Them
https://mehmetgoekce.substack.com/p/b-trees-why-every-database-uses-them