Специфичные индексы

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

Работает как обычная хэш-таблица. База пропускает ключ через хэш-функцию и мгновенно получает адрес строки. Это дает сложность O(1) — поиск по миллиону UUID или длинных URL происходит моментально.

Вместо дерева здесь используются битовые векторы (массивы из 0 и 1). Это идеально работает, когда у данных мало уникальных значений (Low Cardinality). Например, пол, статус заказа или страна.

Почему это быстро: Процессоры умеют делать битовые операции (AND/OR) на аппаратном уровне невероятно быстро. Если тебе нужно найти «Всех мужчин ИЗ Германии СО статусом Active», база просто сложит три битовые маски. Но будь осторожен: любая запись (INSERT) блокирует весь Bitmap-индекс, поэтому их используют только в аналитических хранилищах.

Если B-Tree ищет строку целиком, то инвертированный индекс разбирает её на части (токены). Он хранит словарь слов, где для каждого слова записан список ID документов, в которых оно встречается.

• Где встречается: Основа Elasticsearch и Lucene. В PostgreSQL реализован через модуль GIN (Generalized Inverted Index).
• Задача: Полнотекстовый поиск, поиск по элементам JSON-массивов.

Обычное дерево не понимает, что такое «находиться внутри круга» или «пересекать полигон». Для этого используются R-деревья, которые группируют объекты в иерархию прямоугольников (Bounding Boxes).