Что такое индекс и как он работает на физическом уровне, за счёт чего происходит ускорение?

Индекс в базе данных — это структура данных, которая ускоряет поиск и сортировку записей. На физическом уровне индекс обычно реализуется как сбалансированное дерево (например, B-дерево) или хеш-таблица.

Идея в том, что вместо последовательного перебора всех строк таблицы, СУБД обращается к индексу, который содержит отсортированные ключи и ссылки на соответствующие записи. Это позволяет быстро находить нужные данные по ключу.

Ускорение достигается за счёт:

• уменьшения количества операций чтения с диска (индекс компактнее и организован для быстрого поиска);
• использования структур с логарифмическим временем поиска (B-дерево);
• возможности быстро фильтровать и сортировать данные без полного сканирования таблицы.

Например, если есть индекс по столбцу "id", поиск записи с конкретным id происходит за O(log n), а не за O(n).