Почему чаще всего используется B-tree индекс и какая у него алгоритмическая сложность

Что проверяют

Понимаете ли вы, что выбор структуры продиктован дисковым вводом-выводом, а не только асимптотикой.

Как отвечать

Сложность поиска, вставки и удаления O(log n). Важна не сама оценка, а основание логарифма: узел B-дерева равен странице (в PostgreSQL 8 КБ) и хранит сотни ключей, поэтому ветвление огромное. На практике дерево для таблицы в сотни миллионов строк имеет высоту три или четыре, то есть запрос это три или четыре обращения к страницам, причём верхние уровни почти всегда уже в буферном кэше.

Почему именно эта структура стала основной:

• работает с диском, а не с памятью: узел равен единице чтения. Сбалансированное двоичное дерево имеет ту же асимптотику, но каждый спуск это отдельное обращение к странице, а их будет три десятка вместо трёх;
• универсальность: один индекс обслуживает равенство, диапазоны (>, <, BETWEEN), сортировку (ORDER BY без отдельной сортировки), поиск по префиксу строки, MIN и MAX, а также условие по первым колонкам составного индекса. Хеш-индекс умеет только равенство;
• упорядоченность: листья связаны в список, поэтому чтение диапазона идёт последовательно;
• самобалансировка: высота остаётся одинаковой для всех ключей при любых вставках;
• поддержка уникальности и работа с NULL.

В PostgreSQL это nbtree, вариант B+-дерева: данные только в листьях, внутренние узлы это разделители.

Когда берут другое: GIN для полнотекстового поиска и jsonb, GiST для геометрии, BRIN для огромных таблиц с естественным порядком по времени, хеш для строгого равенства по длинным значениям. Все они узкие, поэтому по умолчанию остаётся B-дерево.

Где спотыкаются

Называют O(log n) и не могут объяснить, почему это лучше двоичного дерева.

Считают, что хеш-индекс всегда быстрее из-за O(1).

Не знают, что B-дерево обслуживает сортировку.

Путают B-дерево и B+-дерево и не понимают, зачем данные вынесены в листья.