B-дерево (B-tree) — сбалансированное дерево с большим коэффициентом ветвления. Поиск за O(log n) вместо O(n) при полном переборе.
Ключевая идея: каждый узел содержит много ключей (сотни), и дерево очень неглубокое. Для таблицы в миллион строк — 3-4 уровня. Каждый уровень — одно чтение с диска.
При переборе миллиона строк нужно прочитать все данные. При B-дереве — 3-4 страницы. Именно поэтому индексы в PostgreSQL и MySQL используют B-tree по умолчанию. Дополнительный бонус: B-дерево хранит данные отсортированными, поэтому range-запросы тоже быстрые.