Ответ
Оценка сводится к пониманию структуры индекса и стоимости операций доступа. В реальной работе я смотрю на план запроса (EXPLAIN ANALYZE) и оцениваю, соответствует ли выбранный доступ ожидаемой сложности.
Основные структуры и их сложность:
| Тип индекса | Структура данных | Поиск по ключу (=) |
Диапазонный поиск (BETWEEN, >) |
Вставка / Удаление | Типичное применение в БД |
|---|---|---|---|---|---|
| B-дерево (B+tree) | Сбалансированное дерево | O(log n) | O(log n + k) (k - кол-во записей в диапазоне) | O(log n) | PostgreSQL, MySQL (InnoDB), SQL Server. Универсальный выбор. |
| Хеш-индекс | Хеш-таблица | O(1) в среднем | Не поддерживается | O(1) в среднем | PostgreSQL, MySQL (MEMORY). Только для точечных запросов. |
| Bitmap-индекс | Битовые массивы | O(1) для AND/OR |
Неэффективно | O(n) в худшем | Колоночные СУБД (ClickHouse). Для низкокардинальных полей (пол, статус). |
Практическая оценка на примере PostgreSQL:
- Смотрю план запроса. Ожидаю увидеть
Index ScanилиIndex Only Scanдля поиска по индексированному полю.EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 12345; -- user_id проиндексирован -- В плане должно быть: Index Scan using idx_orders_user_id on orders ... - Оцениваю стоимость. Операция
Index Scanсостоит из:- Проход по дереву индекса: O(log n).
- Обращение к таблице (heap fetch) по TID: +1 операция чтения на каждую найденную строку. Если индекс
covering(включает все нужные поля), происходитIndex Only Scanи второе чтение не нужно.
- Для составного индекса
(A, B)сложность поиска поA— O(log n), а поиск только поB— O(n) (полный сканирование индекса), так как префикс ключа не задан.
Что влияет на реальную производительность, помимо Big O:
- Размер страницы/блока БД: B-дерево оптимизировано под пакетное чтение с диска.
- Фактор кластеризации (CLUSTER): Если данные в таблице физически упорядочены по ключу индекса, снижаются затраты на heap fetch.
- Селективность: Индекс выгоден, если он отфильтровывает большую часть данных. Для неселективных полей (например,
status = 'active', где 90% строк) полное сканирование таблицы может быть быстрее.