B-дерево обеспечивает поиск за O(log n) с очень маленьким основанием логарифма — потому что каждый узел хранит сотни ключей.
Почему это важно для дисков:
- Каждый уровень дерева = одно чтение страницы (обычно 8-16 KB)
- Узел 8KB с ключами по 8 байт = ~500 ключей в узле
- 500^3 = 125 миллионов записей за 3 чтения с диска
B+ дерево (вариант для БД): данные только в листьях, листья связаны в список — эффективные range scans. Внутренние узлы содержат только ключи-разделители, поэтому ветвление ещё больше.
PostgreSQL использует B-tree для всех стандартных индексов (btree — тип по умолчанию).