Почему индексы в базах данных устроены как B-дерево?

Диск (и даже SSD) читает не байты, а страницы, и случайное чтение дорогое. Значит, структура поиска должна минимизировать число прочитанных страниц.

Бинарное дерево поиска для миллиарда ключей имеет высоту не меньше 30; каждый узел — отдельная страница, итого ~30 случайных чтений. И даже сбалансированное (AVL, красно-чёрное) плохо ложится на страницы.

B-дерево делает узел размером со страницу. В странице 8 КБ помещаются сотни ключей с указателями — коэффициент ветвления 200–500. Тогда:

• 2 уровня — до 250 тыс. ключей;
• 3 уровня — до 60 млн;
• 4 уровня — до 15 млрд.

Корень и верхние уровни почти всегда в кэше, поэтому поиск — 1–2 реальных чтения. Внутри узла ключи отсортированы, и нужный указатель находится бинарным поиском.

Вставка. Ключ кладётся в нужный лист. Если лист переполнен, он делится пополам, а средний ключ поднимается в родителя; если переполнился родитель — делится и он. Корень делится — появляется новый корень, высота растёт на 1 для всех листьев сразу. Поэтому дерево всегда идеально сбалансировано. Удаление может сливать недозаполненные узлы.

B+-дерево — вариант, который используют почти все СУБД: во внутренних узлах только ключи-разделители, сами записи (или ссылки на них) — в листьях, а листья связаны в список. Диапазонный запрос находит начало и идёт по листьям подряд — это и BETWEEN, и ORDER BY без сортировки.

Что из этого следует для запросов:

• индекс работает для равенства, диапазонов, сортировки и префикса строки (LIKE 'ab%'), но не для LIKE '%ab' и не для функции от колонки без функционального индекса;
• составной индекс (a, b) отсортирован сначала по a — поэтому поиск по одному b его не использует;
• вставка случайных ключей (UUIDv4) раскидывает записи по всем листьям: больше разделений, кэш хуже — отсюда интерес к UUIDv7 и автоинкременту;
• каждый индекс — отдельное дерево, которое нужно обновлять при записи.

В InnoDB таблица сама хранится как B+-дерево по первичному ключу (кластерный индекс), а вторичные индексы хранят первичный ключ. В PostgreSQL таблица — куча, а индексы ссылаются на физический адрес строки.

Таблица на 100 млн строк, ключ bigint (8 байт) + указатель (6 байт),
страница 8 КБ → ~500 ключей на узел.
log_500(100 000 000) ≈ 2,96 → 3 уровня: корень → внутренний узел → лист.
Корень и внутренние узлы в памяти — поиск = 1 чтение листа.