Ответ
B-дерево и его вариант B+дерево — это стандарт для индексов в реляционных СУБД, оптимизированный для сбалансированных операций чтения/записи на диске. Однако для специфичных сценариев используются другие структуры:
1. Хеш-индекс (Hash Index)
- Принцип: Использует хеш-таблицу. Идеально подходит для поиска по точному совпадению (
WHERE key = value). - Плюсы: Сложность поиска O(1) в среднем.
- Минусы: Не поддерживает диапазонные запросы (
BETWEEN,>,<), частичное совпадение или сортировку по ключу. - Где используется: InnoDB в MySQL для адаптивных хеш-индексов в памяти, некоторые NoSQL-хранилища.
2. LSM-дерево (Log-Structured Merge-Tree)
- Принцип: Оптимизировано для очень высокой скорости записи. Записи сначала добавляются в упорядоченную структуру в памяти (memtable), затем сбрасываются на диск в SSTable-файлы, которые периодически мержатся.
- Плюсы: Превосходная производительность записи, часто лучше сжатие.
- Минусы: Чтение может быть медленнее (проверка нескольких уровней), требуется компрессия.
- Где используется: Cassandra, RocksDB (под капотом у многих систем, включая MySQL MyRocks), LevelDB.
3. R-дерево (R-tree) и его варианты (GiST, SP-GiST)
- Принцип: Пространственный индекс для многомерных данных (географические координаты, полигоны).
- Где используется: PostgreSQL (типы данных
geometry,geography), GIS-системы.
4. Инвертированный индекс (Inverted Index)
- Принцип: Используется для полнотекстового поиска. Сопоставляет слова (токены) с документами, в которых они встречаются.
- Где используется: PostgreSQL (
tsvector), Elasticsearch, специализированные поисковые движки.
5. Bitmap-индекс
- Принцип: Для каждого уникального значения столбца создается битовая карта строк. Эффективен для столбцов с низкой кардинальностью (пол, статус).
- Плюсы: Очень эффективен для сложных запросов с
AND/ORнад несколькими такими индексами. - Минусы: Дорого обновлять при частых
INSERT/UPDATE/DELETE. - Где используется: Чаще в колоночных хранилищах данных (OLAP) и системах бизнес-аналитики.
