Ответ
Время доступа к записи в таблице с миллионами строк в первую очередь определяется наличием подходящего индекса.
С индексом (по первичному ключу или другому индексированному полю):
- Сложность: O(log n), где n — количество записей. Для B-дерева (стандартная структура индекса в MySQL/PostgreSQL) это означает, что для поиска среди 10 млн записей потребуется всего ~23 сравнения (log2(10^7)).
- Фактическое время: Обычно составляет менее 10 миллисекунд (часто 1-3 мс) для точечного запроса (
WHERE id = ?), если данные находятся в оперативной памяти (InnoDB buffer pool).
Без индекса (или с неподходящим индексом):
- Сложность: O(n). СУБД выполняет полное сканирование таблицы (Full Table Scan).
- Фактическое время: Может занимать сотни миллисекунд или даже секунды на больших таблицах, так как необходимо прочитать с диска и проверить каждую строку.
Пример на SQL:
-- Быстро (~1-3 мс): используется индекс по первичному ключу `id`
SELECT * FROM users WHERE id = 123456;
-- Быстро (~1-10 мс): используется составной индекс `(department_id, status)`
SELECT * FROM orders WHERE department_id = 5 AND status = 'shipped';
-- Медленно (может быть >1000 мс): full scan, т.к. поиск по неиндексированному полю
SELECT * FROM users WHERE bio LIKE '%expert%';
-- Медленно (может быть >1000 мс): full scan, т.к. функция `UPPER()` не позволяет использовать индекс по `email`
SELECT * FROM users WHERE UPPER(email) = 'TEST@EXAMPLE.COM';Вывод: Ключевой фактор производительности — правильное проектирование и использование индексов под реальную нагрузку запросов. Всегда анализируйте план выполнения запроса (EXPLAIN / EXPLAIN ANALYZE).