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

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

Знаете ли вы, что B-tree не единственный вариант, и умеете ли подобрать индекс под тип данных и оператор запроса. Для Node.js-разработчика это обычно PostgreSQL через pg, Prisma или TypeORM. Следом часто спрашивают, как ускорить поиск по jsonb или по LIKE '%...%'.

Как отвечать

Отвечайте на примере PostgreSQL, в нём набор самый широкий:

• Hash: только оператор =. С PostgreSQL 10 пишется в WAL и безопасен, но не поддерживает уникальность, несколько колонок и сортировку, поэтому выигрыш перед B-tree редко оправдывает ограничения;
• GIN: обратный индекс, где на каждое значение хранится список строк. Подходит для jsonb с операторами @> и ?, массивов, полнотекстового поиска по tsvector, а с расширением pg_trgm ускоряет LIKE '%слово%' и ILIKE. Обновляется дороже B-tree;
• GiST: дерево для отношений «пересекается», «содержит», «ближайший». Геоданные в PostGIS, диапазоны вроде tstzrange, поиск ближайших через ORDER BY ... <->, ограничения EXCLUDE для броней без пересечений;
• SP-GiST: несбалансированные разбиения пространства, квадродеревья и префиксные деревья. Точки, IP-адреса, строки с общими префиксами;
• BRIN: минимум и максимум на диапазон блоков. Занимает в сотни раз меньше B-tree, но работает, только если порядок значений совпадает с физическим порядком строк, как у created_at в журнале событий.

Если в проекте есть поиск по эмбеддингам, назовите расширение pgvector с индексами HNSW и IVFFlat.

У MongoDB, которую часто берут в Node-проектах, свой набор: составные, multikey по массивам, текстовые, 2dsphere, hashed и TTL-индексы.

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

Называют bitmap-индекс типом PostgreSQL. Постоянных bitmap-индексов в нём нет, битовые карты строятся на лету при Bitmap Index Scan поверх обычных индексов. Как отдельный тип они есть в Oracle.

Предлагают GIN на всё подряд. На таблице с частыми вставками его поддержка заметно замедляет запись.

Перечисляют типы, но не называют оператор. Индекс помогает только запросу с поддерживаемым оператором: GIN по jsonb не ускорит data->>'name' = 'x', для этого нужен B-tree по выражению.