Мы глубоко разобрали двух титанов: B-Tree семейство (идеально для OLTP, точечных чтений и диапазонов) и LSM-Tree (идеально для write-heavy нагрузок). Но мир индексов на этом не заканчивается.
Чтобы решать специфичные задачи — искать геолокации, фильтровать аналитику или делать полнотекстовый поиск — инженеры адаптировали другие структуры данных. Все их можно разделить на две большие категории:
- Надстройки над B-Tree: Различные подходы к физическому хранению данных внутри классического дерева (Clustered, Non-Clustered, Covering).
- Альтернативные структуры (Специфичные): Хэш-таблицы, Битовые векторы (Bitmap), Инвертированные индексы и Пространственные деревья (R-Tree).
| Концепция индекса | Базовая структура данных | Где встречается (Примеры) |
|---|---|---|
| Clustered / Non-Clustered | B+ Tree | InnoDB (MySQL), SQL Server |
| Covering (INCLUDE) | B+ Tree с расширенными листьями | PostgreSQL, MySQL |
| Hash | Хэш-таблица (Массив бакетов) | PostgreSQL, In-Memory БД |
| Bitmap | Битовые векторы + RLE сжатие | OLAP: Vertica, StarRocks |
| Inverted | Словарь терминов + Постинг-листы | Elasticsearch, Lucene, GIN в PG |
| Spatial (Пространственный) | Сбалансированное R-Tree / KD-Tree | PostGIS, Oracle Spatial |
Дальше мы пройдемся по каждому из них и разберем, как они работают под капотом.