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

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

Кроме B-tree в базах данных используются hash-индексы (для точного поиска по равенству), bitmap-индексы (для низкокардинальных данных), GiST и GIN (для полнотекстового и геопространственного поиска), а также inverted index (в поисковых системах вроде Elasticsearch). В контексте frontend и Node.js чаще всего встречаются hash-индексы в MongoDB и inverted index в памяти для поиска по массивам.

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

B-tree - универсальный индекс для большинства сценариев, но существуют специализированные типы:

• Hash-индекс: хранит хеш-значения ключей, работает только для операций равенства (=, IN). Быстрее B-tree для точного поиска, но не поддерживает range-запросы и сортировку. Используется в PostgreSQL (hash access method) и MongoDB (hashed index для шардирования).

• Bitmap-индекс: представляет каждый уникальный ключ как битовую маску. Эффективен для низкокардинальных данных (пол, статус, категория). Позволяет быстро выполнять битовые операции (AND, OR) для комбинированных запросов. Используется в Oracle, PostgreSQL (с расширением).

• GiST (Generalized Search Tree): обобщённое дерево поиска для нестандартных типов данных - геометрических (R-tree), полнотекстовых, массивов. Поддерживает операции "пересекается", "содержит", "близко к".

• GIN (Generalized Inverted Index): инвертированный индекс для композитных значений - массивы, JSON, полнотекстовый поиск. Хранит отображение элементов на документы, их содержащие. Используется в PostgreSQL для полнотекстового поиска и индексации JSONB.

• Inverted index: основа поисковых систем (Elasticsearch, Solr). Строит словарь термов со списками документов. Поддерживает ранжирование по TF-IDF, BM25.

• BRIN (Block Range Index): для больших таблиц с естественной сортировкой (логи, временные ряды). Хранит минимальные и максимальные значения для блоков страниц. Компактнее B-tree, но менее точный.

• Spatial index (R-tree, Quadtree): для геопространственных данных. Используется в MongoDB (2dsphere), PostgreSQL (PostGIS).

На практике

В frontend-разработке и Node.js индексы обычно используются через ORM/ODM или базы данных:

• MongoDB: по умолчанию B-tree для _id, но для геоданных - 2dsphere (R-tree), для шардирования - hashed index. Для полнотекстового поиска - text index (inverted index).

• PostgreSQL через Node.js: GIN для JSONB-полей (например, хранение метаданных), GiST для геоданных, hash-индексы для точного поиска по email.

• Elasticsearch: inverted index для полнотекстового поиска, BKD-деревья для числовых полей.

• Redis: hash-таблицы (не B-tree) для кэша, Sorted Sets (skiplist) для рейтингов.

Пример: в приложении на Node.js с PostgreSQL для поиска по тегам (массив строк) используется GIN-индекс:

SQL
CREATE INDEX idx_articles_tags ON articles USING GIN (tags);

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

Начни с перечисления основных типов, затем сфокусируйся на тех, что релевантны твоему стеку. Для senior-позиции важно показать понимание trade-off: когда hash-индекс выгоднее B-tree (точное совпадение, нет сортировки), когда GIN (поиск по массивам), когда bitmap (низкая кардинальность). Приведи пример из практики - например, выбор GIN для JSONB в PostgreSQL вместо B-tree при работе с динамическими полями. Упомяни, что в Node.js чаще работаешь с индексами через ORM (Sequelize, TypeORM, Prisma), но понимание внутреннего устройства помогает оптимизировать запросы.

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

• Широта знаний за пределами стандартного B-tree.
• Понимание trade-off между типами индексов.
• Умение применять знания к конкретному стеку (JavaScript, Node.js, Java).
• Глубина: знание не только названий, но и внутреннего устройства (например, как GIN хранит отображения).
• Практический опыт: когда и почему выбирал конкретный тип индекса.

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

• Называть только B-tree и hash, забывая про GIN, GiST, bitmap.
• Путать hash-индекс с хеш-таблицей в памяти - в БД hash-индекс не поддерживает range-запросы.
• Думать, что все индексы в MongoDB - B-tree (на самом деле text, 2dsphere, hashed - другие).
• Не учитывать кардинальность данных: bitmap-индекс на поле с уникальными значениями бесполезен.
• Предлагать GIN для простых числовых полей - там B-tree эффективнее.
• Забывать про overhead: GIN и GiST медленнее на запись, чем B-tree.