Расскажи про виды индексов

Виды индексов в базах данных

Индекс — это структура данных, которая ускоряет поиск информации в таблице. Подобно указателю в книге: вместо чтения всех страниц вы можете перейти на нужную по индексу.

Основная идея

-- Без индекса: полное сканирование таблицы O(n)
SELECT * FROM users WHERE id = 12345;
-- Проверяем все 1,000,000 строк

-- С индексом: бинарный поиск O(log n)
CREATE INDEX idx_users_id ON users(id);
SELECT * FROM users WHERE id = 12345;
-- Проверяем ~20 строк из 1,000,000

1. B-Tree индекс (B-Search Tree)

Самый универсальный и распространённый тип.

CREATE INDEX idx_users_email ON users(email);

Структура:

         [M]
        /   \
      [D]   [T]
     / \   / \
   [A][G][P][Z]

Дерево сбалансировано, глубина O(log n). Каждый узел может содержать несколько значений.

Преимущества:

• Работает для диапазонов: WHERE age BETWEEN 18 AND 65
• Сортировка: ORDER BY name
• Быстрый поиск по точному значению

Недостатки:

• Занимает место в памяти
• Замедляет INSERT/UPDATE/DELETE (нужно обновлять индекс)

Примеры использования:

-- Точный поиск
SELECT * FROM users WHERE id = 100;

-- Диапазон
SELECT * FROM users WHERE created_at > 2024-01-01;

-- LIKE с префиксом
SELECT * FROM users WHERE email LIKE user@%;

2. Hash индекс

Быстро для точного поиска, но без диапазонов.

CREATE INDEX idx_users_id USING HASH ON users(id);

Структура:

Hash функция: hash("john@example.com") = 42
Таблица хеша:
[42] → указатель на строку в БД
[87] → указатель на строку в БД

Преимущества:

• Очень быстрый точный поиск O(1)
• Меньше памяти на разреженных данных

Недостатки:

• Не поддерживает диапазоны: WHERE age > 18 — не может использовать
• Не поддерживает сортировку
• На коллизии хеша медленнее B-Tree

Примеры использования:

-- Быстро
SELECT * FROM users WHERE id = 100;

-- НЕ поддерживается Hash индексом
SELECT * FROM users WHERE id > 100;    -- Full scan!
SELECT * FROM users ORDER BY id;       -- Full scan!

3. Bitmap индекс

Отлично для низкокардинальных данных (мало уникальных значений).

Поля: gender (M/F)
Rows:  [M, F, M, M, F, F, M]

Bitmap для M: [1, 0, 1, 1, 0, 0, 1]
Bitmap для F: [0, 1, 0, 0, 1, 1, 0]

Используется в:

• Oracle Database
• GreenPlum
• PostgreSQL (условно, через bitsets)

Преимущества:

• Супер компактный (всего несколько байт на миллион строк)
• Быстрые логические операции (AND, OR)

Недостатки:

• Только для низкокардинальных столбцов (gender, status, is_active)
• Медленный INSERT (нужно переписать весь bitmap)

Примеры использования:

-- Идеально
SELECT * FROM users WHERE gender = M AND is_active = 1;

-- Плохо (высокая кардинальность)
SELECT * FROM users WHERE email_hash = 12345;  -- Better use B-Tree

4. Full-Text индекс

Для поиска по текстовым полям.

CREATE FULLTEXT INDEX ft_idx ON articles(content);
SELECT * FROM articles WHERE MATCH(content) AGAINST(machine learning IN BOOLEAN MODE);

Как работает:

Текст: "machine learning is fun"

Inverted Index (обратный индекс):
machine → [doc_1, doc_5, doc_12]
learning → [doc_1, doc_3]
fun → [doc_2, doc_5]

Преимущества:

• Поиск по словам, фразам, логическим операциям
• Релевантность результатов (ranking)
• Поддержка синонимов

Недостатки:

• Занимает много места
• Специфичен для текстовых данных

Примеры:

-- Простой поиск
SELECT * FROM articles WHERE MATCH(title) AGAINST(database);

-- Boolean режим
SELECT * FROM articles 
WHERE MATCH(content) AGAINST(+database -NoSQL IN BOOLEAN MODE);
-- database обязателен, NoSQL исключён

5. BRIN индекс (Block Range Index)

Для больших таблиц с упорядоченными данными.

Доступен в PostgreSQL.

CREATE INDEX idx_events_date ON events USING BRIN (created_at);

Как работает:

Таблица разбита на блоки (обычно 128 строк)
Для каждого блока хранятся min/max значения:

Блок 1: min_date = 2024-01-01, max_date = 2024-01-31
Блок 2: min_date = 2024-02-01, max_date = 2024-02-28

Запрос WHERE created_at > 2024-01-15:
→ Блок 1: может содержать (проверить)
→ Блок 2: не содержит (пропустить)

Преимущества:

• Минимальный размер (килобайты для таблиц в гигабайты)
• Отлично для очень больших таблиц
• Может быстро исключить целые блоки

Недостатки:

• Работает только с упорядоченными данными
• Медленнее B-Tree на точных совпадениях

Примеры:

-- Отлично (таблица временных рядов)
CREATE INDEX idx_metrics_timestamp ON metrics USING BRIN (timestamp);
SELECT * FROM metrics WHERE timestamp > NOW() - INTERVAL 7 days;

-- Плохо
CREATE INDEX idx_users_random ON users USING BRIN (random_hash);
-- Индекс неэффективен, так как данные не упорядочены

6. Partial индекс

Индекс только для части таблицы.

CREATE INDEX idx_active_users ON users(email) WHERE is_active = true;

Преимущества:

• Меньше памяти (индексируем только 10% таблицы)
• Быстрее обновления

Примеры:

-- Индекс только для недавних заказов
CREATE INDEX idx_recent_orders ON orders(customer_id) 
WHERE created_at > NOW() - INTERVAL 90 days;

-- Индекс только для неудалённых товаров
CREATE INDEX idx_active_products ON products(category) 
WHERE deleted_at IS NULL;

7. Multicolumn индекс (Composite index)

Индекс по нескольким столбцам.

CREATE INDEX idx_users_country_city ON users(country, city);

Как работает:

Сначала сортирует по country, затем по city
Дерево:
  USA
  ├─ New York
  ├─ Los Angeles
  └─ Chicago
  UK
  ├─ London
  └─ Manchester

Примеры:

-- Используется индекс (оба столбца в WHERE)
SELECT * FROM users WHERE country = USA AND city = NYC;

-- Используется индекс (префикс)
SELECT * FROM users WHERE country = USA;

-- НЕ используется индекс полностью (не с начала)
SELECT * FROM users WHERE city = NYC;
-- Придётся сканировать весь индекс

8. JSON индекс

Для поиска в JSON полях.

CREATE INDEX idx_user_metadata ON users USING GIN (metadata);
SELECT * FROM users WHERE metadata->status = premium;

Доступен в:

• PostgreSQL (GIN, JSONB)
• MySQL 5.7+
• MongoDB

9. Spatial индекс (GiST, BRIN)

Для географических данных.

CREATE INDEX idx_locations ON places USING GIST (location);
SELECT * FROM places 
WHERE ST_DWithin(location, POINT(37.7749 -122.4194)::geography, 1000);

Используется для:

• Карт и геолокации
• Поиск ближайших точек
• Пересечение регионов

Сравнение типов индексов

Правила создания индексов

-- ✓ ХОРОШО: часто используемые столбцы в WHERE
CREATE INDEX idx_users_email ON users(email);

-- ✓ ХОРОШО: multicolumn для частых комбинаций
CREATE INDEX idx_orders_user_date ON orders(user_id, created_at);

-- ✓ ХОРОШО: partial индекс для фильтра
CREATE INDEX idx_active_users ON users(email) WHERE is_active = true;

-- ✗ ПЛОХО: индекс на редко используемый столбец
CREATE INDEX idx_rarely_used ON users(metadata);

-- ✗ ПЛОХО: слишком много индексов (замедляет INSERT)
CREATE INDEX idx1 ON users(col1);
CREATE INDEX idx2 ON users(col2);
CREATE INDEX idx3 ON users(col3);
-- ... 20 индексов всего

Проверка эффективности индекса

-- PostgreSQL: посмотреть, используется ли индекс
EXPLAIN ANALYZE
SELECT * FROM users WHERE email = john@example.com;

-- Результат:
-- Bitmap Heap Scan on users  (cost=4.29..5.54 rows=1 width=...)
--   Recheck Cond: (email = john@example.com)
--   ->  Bitmap Index Scan on idx_users_email
-- Индекс используется!

Заключение

Выбор индекса зависит от:

• B-Tree: универсальный выбор для большинства случаев
• Hash: точный поиск в памяти
• Bitmap: низкокардинальные данные (gender, status)
• BRIN: очень большие упорядоченные таблицы
• Full-Text: текстовый поиск
• GiST/BRIN: пространственные данные

Не создавайте индексы "на всякий случай" — каждый индекс замедляет INSERT/UPDATE/DELETE. Используйте EXPLAIN ANALYZE для проверки эффективности.