Сколько выполняется поиск по индексу в базе данных?

Время поиска по индексу не является константой. Оно описывается асимптотической сложностью, которая зависит от типа индекса и количества записей. На практике на скорость также влияет множество физических факторов.

Теоретическая сложность (Big O notation):

• B-дерево (B-tree, B+tree) — самый распространенный индекс в PostgreSQL, MySQL, SQL Server. Сложность поиска по уникальному значению — O(log n), где n — число записей в индексе. Это означает, что для поиска в таблице из 1 миллиона записей потребуется всего ~20 операций сравнения (log₂(1M) ≈ 20).
• Хеш-индекс (Hash index) — доступен в PostgreSQL и других СУБД. Средняя сложность поиска — O(1), но в худшем случае (при многих коллизиях) может деградировать до O(n). Подходит только для операций строгого равенства (=).
• Bitmap-индекс — эффективен для колонок с низкой селективностью (малое количество уникальных значений, например, status). Скорость зависит от эффективности битовых операций (AND, OR).

Практические факторы, влияющие на время:

1. Селективность запроса: Поиск по уникальному ключу (WHERE id = 123) почти мгновенен. Поиск по неселективному индексу (WHERE active = true, когда 90% строк true) может привести к чтению почти всех страниц индекса, и оптимизатор может выбрать полное сканирование таблицы.
2. Размер и глубина дерева: Индекс по INT будет меньше и быстрее, чем по строке VARCHAR(500). Глубина B-дерева обычно 3-4 уровня для очень больших таблиц.
3. Физическое расположение данных: Если индекс сильно фрагментирован (много пустого пространства после удалений), поиск будет медленнее из-за большего количества чтений с диска. Требуется перестроение индекса (REINDEX).
4. Тип доступа: INDEX UNIQUE SCAN (поиск одного значения) быстрее, чем INDEX RANGE SCAN (поиск по диапазону, например, WHERE date > '2023-01-01'), который читает множество листовых страниц индекса.

Пример и демонстрация: В PostgreSQL можно использовать EXPLAIN (ANALYZE, BUFFERS) для оценки.

-- Создаем индекс
CREATE INDEX idx_orders_user_id ON orders(user_id);

-- Анализируем план быстрого поиска по индексу
EXPLAIN (ANALYZE, BUFFERS) 
SELECT * FROM orders WHERE user_id = 4567;

-- В выводе будет что-то вроде:
-- Index Scan using idx_orders_user_id on orders  (cost=0.29..8.31 rows=1 width=45) (actual time=0.025..0.026 rows=2 loops=1)
--   Index Cond: (user_id = 4567)
-- Planning Time: 0.115 ms
-- Execution Time: 0.045 ms  -- Вот это фактическое время выполнения
-- Buffers: shared hit=4      -- Все данные были в кэше (RAM)

Итог: Для таблицы в десятки миллионов строк поиск по хорошему B-дереву индексу обычно занимает доли миллисекунд, если данные в памяти, или несколько миллисекунд, если требуется чтение с диска. Это на порядки быстрее полного сканирования (O(n)).