Что такое индексы в БД: B-Tree и Hash, и как они ускоряют поиск?

B-Tree хранит упорядоченные ключи и подходит для равенства, диапазонов и сортировки; Hash организует поиск по хешу и обычно применяется к проверкам равенства.

Индекс позволяет найти подходящие записи без просмотра всей таблицы. У сбалансированного дерева поиск требует логарифмического числа шагов по структуре, а соседние ключи удобны для диапазонов. Хеш-индекс использует бакеты, но коллизии и особенности реализации не позволяют обещать неизменно O(1). Индексы занимают место и замедляют запись, поэтому их выбирают по реальным запросам и планам выполнения. Оптимизатор может предпочесть последовательное чтение, если запрос возвращает большую часть таблицы.