Что такое B-дерево и почему оно используется в базах данных и файловых системах?

B-дерево — сбалансированное дерево поиска, где в узле хранятся сотни ключей, а все листья на одной глубине; узел подгоняют под размер страницы диска, и поиск среди миллиардов записей укладывается в 3–4 чтения страниц.

Устройство

• Узел порядка m содержит до m−1 ключей и до m детей; каждый узел, кроме корня, заполнен хотя бы наполовину.
• Высота ≈ log_m(n): при ветвлении 500 четыре уровня вмещают больше 60 млрд ключей.
• Вставка: если лист полон, он делится пополам, средний ключ поднимается в родителя; дерево растёт вверх через разделение корня, поэтому остаётся идеально сбалансированным.

B+-дерево — то, что в реальных системах

• Данные или ссылки на строки лежат только в листьях, внутренние узлы — лишь разделители, поэтому ветвление ещё выше.
• Листья связаны в список: диапазонный запрос WHERE ts BETWEEN … — спуск к началу диапазона и последовательное чтение.
• InnoDB хранит таблицу как кластерный индекс B+-дерева на страницах по 16 КБ, PostgreSQL строит btree-индексы на страницах по 8 КБ.
• Файловые системы: Btrfs, XFS, NTFS, APFS — B-деревья для каталогов, экстентов и метаданных.

Компромиссы

• Отлично для чтения и диапазонов, но случайные вставки вызывают разделения страниц и запись в произвольные места.
• Под интенсивную запись выбирают LSM-деревья (RocksDB, Cassandra): последовательная запись ценой фоновой компакции.

Коротко для собеседования

B-дерево делает узел размером со страницу диска и хранит в нём сотни ключей, поэтому высота мала и поиск укладывается в несколько чтений страниц. В базах используют B+-дерево со связанными листьями, удобное для диапазонов, а при тяжёлой записи смотрят в сторону LSM-деревьев.