> Как индексы в базе данных ускоряют поиск и почему поиск по индексу быстрее полного сканирования (PHP)

Короткий ответ

Индекс - это структура данных (обычно B-tree), которая хранит отсортированные копии значений ключевых колонок со ссылками на строки таблицы. Поиск по индексу работает за O(log n) вместо O(n) при полном сканировании, потому что B-tree позволяет бинарным поиском быстро находить нужный диапазон значений, отбрасывая на каждом уровне дерева половину данных. Полное сканирование читает каждый блок таблицы, а индекс - только несколько уровней дерева и целевые страницы данных.

Подробное объяснение

Когда выполняется запрос без индекса, база данных последовательно читает все страницы таблицы (heap) и проверяет каждую строку на соответствие условию WHERE. Это линейная операция O(n), где n - количество строк. При больших таблицах это означает чтение гигабайтов данных с диска.

Индекс - это отдельная структура, обычно B-tree. В узлах дерева хранятся отсортированные значения ключа и указатели на соответствующие строки в таблице. Высота B-tree для миллиона строк - всего 3-4 уровня. Поиск значения начинается с корня, на каждом уровне сравнивается ключ и выбирается нужная ветвь, отбрасывая примерно половину оставшихся данных. Так достигается O(log n).

Важный нюанс: индекс ускоряет поиск, но не всегда. Если условие WHERE выбирает более 10-20% строк таблицы, оптимизатор может выбрать полное сканирование - потому что чтение индекса плюс случайный доступ к строкам (lookup) обойдётся дороже последовательного чтения. Также индекс бесполезен для операций, которые не могут использовать отсортированность (например, LIKE '%text%' без полнотекстового индекса).

Дополнительно индекс помогает с сортировкой (ORDER BY) и группировкой (GROUP BY), так как данные уже отсортированы. Покрывающий индекс (covering index) содержит все нужные колонки - тогда база вообще не обращается к таблице.

На практике

В MySQL с движком InnoDB первичный ключ - это кластерный индекс: строки хранятся в листьях B-tree, отсортированные по PK. Вторичные индексы хранят значение PK как ссылку на строку. Поэтому при поиске по вторичному индексу происходит два обращения: сначала в индекс, потом в кластерный индекс за строкой.

В PostgreSQL индексы неуникальны по структуре - в листьях хранятся физические адреса строк (ctid). При UPDATE или DELETE строки могут перемещаться, поэтому PostgreSQL использует HOT (heap-only tuples) и autovacuum для поддержания актуальности индексов.

При проектировании важно не плодить индексы без необходимости: каждый индекс замедляет INSERT/UPDATE/DELETE, потому что нужно обновлять и таблицу, и все индексы. Обычно достаточно 3-5 индексов на таблицу, покрывающих основные сценарии выборки.

Пример кода

SQL
-- Создание индекса
CREATE INDEX idx_users_email ON users(email);

-- Запрос, который использует индекс
SELECT * FROM users WHERE email = 'alice@example.com';

-- Проверка плана выполнения в PostgreSQL
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'alice@example.com';
-- Index Scan using idx_users_email on users  (cost=0.29..8.31 rows=1 width=...)
--   Index Cond: (email = 'alice@example.com'::text)

-- Составной индекс для запроса с фильтром и сортировкой
CREATE INDEX idx_orders_user_created ON orders(user_id, created_at);

SELECT * FROM orders 
WHERE user_id = 42 
ORDER BY created_at DESC 
LIMIT 10;
-- Индекс покрывает и фильтр, и сортировку, избегая filesort

Как отвечать на собеседовании

Начни с определения индекса и основной структуры - B-tree. Скажи про сложность O(log n) против O(n). Обязательно упомяни, что индекс - это отдельное хранилище, которое занимает место и замедляет запись. Покажи понимание trade-off: индекс полезен для селективных запросов, но вреден при выборке большой доли строк. Если спросят про конкретную БД - расскажи про кластерный индекс в InnoDB и отличие от heap-таблиц в PostgreSQL. Хорошо добавить пример из практики: когда индекс не сработал из-за функции на колонке или неверного порядка колонок в составном индексе.

Что проверяет интервьюер

• Понимание структуры B-tree и принципа бинарного поиска
• Умение объяснить сложность алгоритмов
• Осознание trade-off между скоростью чтения и записи
• Знание, когда индекс бесполезен или вреден
• Практический опыт: составные индексы, покрывающие индексы, EXPLAIN

Типичные ошибки

• Утверждение, что индекс ускоряет все запросы - это не так, при выборке >10-20% строк полное сканирование быстрее
• Игнорирование влияния индексов на скорость записи
• Непонимание разницы между кластерным и вторичным индексом
• Утверждение, что индекс хранит копию всей таблицы - на самом деле только ключевые колонки и ссылки
• Забывают про покрывающие индексы и возможность избежать обращения к таблице
• Путаница между индексом и полнотекстовым поиском - это разные механизмы