Какие типы индексов кроме B-tree существуют и используются

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

Понимаете ли вы, что набор индексов зависит от конкретной базы, и знаете ли, какие из них доступны вашему Java-сервису. Сильный ответ привязан к СУБД проекта. Следом обычно спрашивают, как такой индекс описать в JPA и почему в итоге его пишут миграцией.

Как отвечать

Сразу оговорите, что ответ зависит от базы, и разберите популярные:

• PostgreSQL: hash для точного равенства; GIN для jsonb, массивов и полнотекстового поиска, с pg_trgm ещё и для LIKE '%...%'; GiST для геоданных, диапазонов и ограничений EXCLUDE; SP-GiST для точек и префиксов; BRIN для огромных таблиц, где значения растут вместе с физическим порядком строк;
• MySQL (InnoDB): строки лежат в кластерном индексе по первичному ключу, а вторичные индексы хранят значение этого ключа. Поэтому длинный первичный ключ раздувает все индексы таблицы. Кроме B-tree есть FULLTEXT и SPATIAL на R-tree, явные хэш-индексы есть у движка MEMORY, а в InnoDB адаптивный хэш строится автоматически;
• Oracle: bitmap-индексы для колонок с малым числом значений в аналитике, индексы по функции, reverse key для последовательных ключей.

Отдельно назовите индексы по выражению и частичные: в PostgreSQL CREATE INDEX ON users (lower(email)) и индекс с WHERE deleted_at IS NULL. Это не новая структура, но на практике их применяют постоянно.

Для Java-стека важно, что @Index из JPA знает только колонки, порядок и уникальность. Тип индекса, выражение и условие через него не описать, поэтому такие индексы пишут SQL-миграцией в Liquibase или Flyway.

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

Говорят, что B-tree плохо работает на больших объёмах. Глубина дерева растёт логарифмически, и на миллиарде строк это четыре или пять уровней.

Называют R-tree отдельным типом PostgreSQL. Его давно заменил GiST, пространственные индексы там строятся через него.

Советуют bitmap-индексы для OLTP. Даже в Oracle они плохо переносят конкурентные изменения: одна запись блокирует участок битовой карты, покрывающий много строк.