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

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

Понимаете ли вы индекс как структуру данных с компромиссами, а не как строчку CREATE INDEX. В Go-проектах рядом с PostgreSQL часто стоят ClickHouse, Elasticsearch или встроенные хранилища, так что стоит выйти за пределы одной базы. Следом обычно спрашивают, чем LSM-дерево отличается от B-tree по нагрузке на запись.

Как отвечать

Сгруппируйте по принципу, а не списком из документации:

• хэш-индекс: точный поиск за O(1), без диапазонов и сортировки. В PostgreSQL это тип hash, в Go тот же принцип у map;
• LSM-дерево: запись идёт в память и журнал, потом сбрасывается на диск отсортированными файлами, которые фоном сливаются. Быстрая запись ценой чтения через несколько уровней. Так устроены RocksDB, Cassandra и написанные на Go Pebble и BadgerDB, а bbolt для контраста хранит данные в B+-дереве;
• фильтр Блума: отвечает «точно нет» или «возможно да», LSM-движки с ним пропускают файлы без нужного ключа;
• обратный индекс: слово в список документов. Полнотекстовый поиск в Elasticsearch, в PostgreSQL его аналог GIN для tsvector, jsonb и массивов;
• пространственные: R-tree и GiST для геоданных, поиск ближайших и пересечений;
• разреженные: одна запись на блок строк. Так работает BRIN в PostgreSQL и первичный индекс ClickHouse, одна метка на гранулу в 8192 строки по умолчанию. Поверх него в ClickHouse есть индексы пропуска данных minmax, set и bloom_filter.

С PostgreSQL из Go обычно работают через pgx, план смотрят EXPLAIN (ANALYZE, BUFFERS), индексы выкатывают миграциями. В goose миграцию с CREATE INDEX CONCURRENTLY помечают -- +goose NO TRANSACTION: внутри транзакции эта команда не работает.

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

Говорят, что LSM всегда быстрее. Он выигрывает на записи, но чтение по ключу обычно дороже, а слияние файлов даёт пики нагрузки на диск.

Переносят привычки из PostgreSQL в ClickHouse и ждут точечного поиска одной строки. Его индексы отсекают целые гранулы, а не находят запись.

Путают фильтр Блума с индексом, который находит данные. Он только отбрасывает лишнее, искать дальше всё равно приходится.