Какова временная сложность поиска записи по её индексу в базе данных?

Временная сложность поиска записи по её индексу в базе данных обычно составляет O(log n), если используется сбалансированное индексное дерево, например B-дерево, которое широко применяется в реляционных СУБД.

Индексы позволяют быстро находить записи без полного перебора таблицы (что было бы O(n)). При наличии индекса поиск сводится к обходу дерева, что даёт логарифмическую сложность.

В некоторых случаях, например, при использовании хеш-индексов, поиск может быть близок к O(1), но это зависит от реализации и типа индекса.

Таким образом, благодаря индексам поиск по ключу в базе данных обычно эффективен и масштабируется хорошо.