Как устроен индекс

Что проверяют

Не список типов, а механику: что лежит на странице индекса, как база по нему находит строку и почему иногда предпочитает читать таблицу целиком. Следом обычно спрашивают про составной индекс и про то, как посмотреть план запроса.

Как отвечать

В PostgreSQL и MySQL (InnoDB) индекс по умолчанию это B+-дерево из страниц фиксированного размера: 8 КБ в PostgreSQL, 16 КБ в InnoDB. Внутренние страницы хранят разделительные ключи и ссылки вниз, листья хранят ключи по порядку и связаны между собой. Дерево широкое, поэтому даже на сотнях миллионов строк до листа три-четыре уровня.

• что в листе: в PostgreSQL ключ и адрес строки в куче (TID). В InnoDB сама таблица лежит в кластерном индексе по первичному ключу, а вторичный индекс хранит значение первичного ключа, так что поиск идёт по двум деревьям;
• как читается: Index Scan ходит в таблицу за каждой строкой, Index Only Scan берёт всё из индекса, если хватает колонок, Bitmap Heap Scan сначала собирает адреса, потом читает страницы по порядку;
• составной индекс: сортировка по первой колонке, внутри по второй, поэтому он работает для левого префикса;
• покрывающий индекс: INCLUDE в PostgreSQL добавляет колонки в листья, чтобы не ходить в таблицу.

Мостик к Java: индексы приходят миграциями Flyway или Liquibase, а не через ddl-auto у Hibernate. Аннотация @Index внутри @Table(indexes = ...) влияет только на генерацию схемы. План смотрите через EXPLAIN (ANALYZE, BUFFERS) на том SQL, который реально генерирует JPA.

Где спотыкаются

Переворачивают кардинальность. Индекс выгоден как раз на колонках с большим числом разных значений, а на колонке «да/нет» почти бесполезен.

Считают, что PostgreSQL сам индексирует внешние ключи. Не индексирует, и JOIN или каскадное удаление по такой колонке превращается в полный проход таблицы. InnoDB такой индекс создаёт сам.

Думают, что индекс используется всегда. Если над колонкой стоит функция, в условии LIKE '%текст' или запрос забирает большую долю таблицы, планировщик выберет последовательное чтение.