Что такое B-дерево и зачем оно в БД?

B-дерево — это сбалансированное дерево, в котором каждый узел может хранить много ключей и иметь много потомков. Именно на нём построены индексы в PostgreSQL и большинстве других баз. Фишка в том, что B-дерево очень мелкое по высоте — даже для миллионов записей достаточно 3-4 уровней, а значит для поиска нужно всего 3-4 чтения с диска. Каждый узел по размеру совпадает со страницей диска (обычно 8KB в Postgres), что минимизирует I/O. Без B-дерева база читала бы всю таблицу последовательно, а с ним — находит нужную строку за логарифмическое время.