> Как индекс определяет, какую запись отдать при поиске по таблице (Go)

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

Индекс - это отдельная структура данных (обычно B-tree или hash), которая хранит отсортированные копии значений ключевых колонок и ссылки на строки таблицы. При поиске СУБД сначала обходит индекс, находит нужные ключи, затем по ссылкам (rowid, primary key или heap pointer) читает сами строки. Индекс не хранит данные таблицы - только ключи и указатели, поэтому поиск по индексу имеет сложность O(log n) вместо полного сканирования O(n).

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

Индекс работает как справочник: вместо перебора всех строк таблицы, СУБД ищет значение в отсортированной структуре. Основные механизмы:

1. Структура индекса - в PostgreSQL и MySQL (InnoDB) это B-tree. Листовые узлы содержат пары "ключ → ссылка на строку". Ссылка - это физический адрес (ctid в PostgreSQL) или первичный ключ (в InnoDB secondary index).

2. Процесс поиска:

   • СУБД получает запрос с условием WHERE col = value
   • Планировщик выбирает индекс, если он есть на col
   • Происходит обход B-tree от корня к листу, сравнивая ключи
   • На листе находится запись с ключом и ссылкой на строку
   • По ссылке выполняется чтение строки из таблицы (это называется lookup или table access by rowid)

3. Типы индексов:

   • Clustered (в InnoDB primary key) - строки физически хранятся в порядке индекса, лист содержит всю строку, lookup не нужен
   • Non-clustered (secondary) - лист содержит только ключ и ссылку, требуется дополнительное чтение строки

4. Покрывающий индекс - если все нужные колонки есть в самом индексе, СУБД не обращается к таблице вообще (index-only scan). Это ключевой приём оптимизации.

5. Селективность - индекс эффективен, когда условие отбирает малый процент строк. Если индекс возвращает >10-15% строк, планировщик может выбрать seq scan, потому что lookup по каждой строке дороже полного сканирования.

6. Стоимость - индекс ускоряет чтение, но замедляет запись: каждая INSERT/UPDATE/DELETE должна обновлять все индексы на таблице. Это trade-off, который нужно учитывать.

На практике

В Go-бэкенде с PostgreSQL или MySQL:

• Индексы создаются через миграции: CREATE INDEX idx_users_email ON users(email)
• ORM (GORM, sqlx) не создают индексы автоматически - это ответственность разработчика
• Для поиска по WHERE user_id = ? в таблице orders нужен индекс на user_id - иначе будет seq scan при росте таблицы
• Составные индексы: порядок колонок критичен. (user_id, created_at) эффективен для WHERE user_id = ? ORDER BY created_at, но бесполезен для WHERE created_at = ?
• В Go важно проверять планы запросов через EXPLAIN ANALYZE - это стандартная практика при оптимизации

Пример кода

GO
// Миграция для создания индекса
// 001_create_indexes.up.sql
CREATE INDEX idx_orders_user_id ON orders(user_id);
CREATE INDEX idx_orders_user_created ON orders(user_id, created_at DESC);

// Проверка плана запроса
// psql: EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 42;
// Результат: Index Scan using idx_orders_user_id on orders

// В Go-коде - обычный запрос, индекс работает на уровне БД
rows, err := db.Query(ctx, "SELECT * FROM orders WHERE user_id = $1", userID)

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

Начни с краткого определения: индекс - это отсортированная структура, которая позволяет находить строки без полного сканирования. Затем опиши механизм: обход B-tree, поиск ключа, чтение строки по ссылке. Упомяни разницу между clustered и non-clustered индексами, а также index-only scan. Обязательно скажи про trade-off: ускорение чтения ценой замедления записи. Если спросят про Go - подчеркни, что индексы управляются на уровне БД, а в коде важно писать запросы, которые могут использовать индексы (не оборачивать колонки в функции, не использовать LIKE '%...').

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

• Понимание внутреннего устройства индексов, а не только синтаксиса CREATE INDEX
• Знание trade-off между скоростью чтения и записи
• Умение объяснить, почему индекс не всегда эффективен (селективность, покрытие)
• Понимание разницы между типами индексов и структур данных
• Практический опыт: когда создавать индекс, как проверять план запроса

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

• Утверждение, что индекс хранит копию всей таблицы - это неверно, он хранит только ключи и ссылки
• Игнорирование стоимости записи: "индексы всегда ускоряют" - нет, они замедляют DML
• Непонимание разницы между clustered и non-clustered индексами
• Создание индексов на каждую колонку без анализа реальных запросов
• Использование SELECT * с индексом - это часто убивает index-only scan, потому что нужны все колонки
• Утверждение, что индекс гарантирует порядок выборки - порядок гарантирован только при ORDER BY в запросе, иначе СУБД может вернуть строки в любом порядке