Как работает индексирование в базах данных? Какие типы индексов существуют?

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

Индекс — это структура данных, которая ускоряет поиск информации в таблице. Без индекса БД выполняет full table scan (проверяет все строки), с индексом — находит нужные данные за O(log n) вместо O(n).

Как работает индекс?

Без индекса (Full Table Scan):

Таблица users (1 млн строк):
[1][2][3][4]...[999999][1000000]
      ↑ нужна строка 5

БД проверяет ВСЕ строки: 1 млн операций

С индексом (B-Tree):

Индекс (сортированное дерево):
        [500000]
       /        \
   [250000]    [750000]
   /    \      /    \
 [125k] [375k] [625k] [875k]
    ↑
  нужна строка 5

БД быстро навигирует по дереву: ~20 операций (log 1000000)

Типы индексов

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

Сбалансированное дерево, наиболее универсальный индекс.

CREATE INDEX idx_users_email ON users(email);

-- Поиск по email: очень быстро
SELECT * FROM users WHERE email = 'user@example.com';
-- Execution time: ~1ms вместо сканирования 1млн строк

Плюсы:

• Работает для =, <, >, <=, >=, BETWEEN
• Поддерживает сортировку (ORDER BY)
• Универсальный

Минусы:

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

2. Hash индекс

Использует хеш-функцию для прямого доступа.

CREATE INDEX idx_user_id_hash ON users USING HASH(user_id);

-- Поиск по точному совпадению: O(1)
SELECT * FROM users WHERE user_id = 12345;

Плюсы:

• Очень быстро для точного совпадения (O(1))
• Занимает меньше памяти чем B-Tree

Минусы:

• Работает только для =, не для <, >, BETWEEN
• Не поддерживает сортировку

3. Full-Text индекс

Для полнотекстового поиска.

CREATE FULLTEXT INDEX idx_article_text ON articles(title, content);

-- Быстрый поиск по тексту
SELECT * FROM articles 
WHERE MATCH(title, content) AGAINST('machine learning' IN BOOLEAN MODE);

Плюсы:

• Поиск по словам, фразам, булевым операторам
• Работает с естественным языком

Минусы:

• Только для текстовых полей
• Требует больше памяти

4. Bitmap индекс

Эффективен для колонок с малым количеством уникальных значений.

-- Хорошо для колонок с мало уникальных значений
CREATE BITMAP INDEX idx_user_status ON users(status);
-- status может быть: 'active', 'inactive', 'banned' (только 3 значения)

Структура:

status = 'active':   [1][1][0][1][1][0][1]...
status = 'inactive': [0][0][1][0][0][1][0]...
status = 'banned':   [0][0][0][0][0][0][0]...

Плюсы:

• Очень быстро для группировки и фильтрации
• Компактно хранит данные

Минусы:

• Только для колонок с малым количеством уникальных значений
• Медленно для INSERT/UPDATE

5. Spatial (GiST, R-Tree) индекс

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

CREATE INDEX idx_location ON places USING GIST(location);

-- Поиск мест рядом с координатой
SELECT * FROM places 
WHERE location <@> POINT(55.7558, 37.6173) <DISTANCE 1000;

Плюсы:

• Поиск по многомерным данным
• Быстро для геопространственных запросов

Минусы:

• Сложнее в понимании
• Занимает больше памяти

6. JSON/JSONB индекс

Для индексирования JSON полей.

CREATE INDEX idx_user_metadata ON users USING GIN(metadata);

-- Быстрый поиск в JSON
SELECT * FROM users 
WHERE metadata->'preferences'->>'theme' = 'dark';

Составные (Composite) индексы

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

-- Индекс по (user_id, created_at)
CREATE INDEX idx_user_transactions ON transactions(user_id, created_at);

-- Работает для:
WHERE user_id = 123;  -- Использует индекс
WHERE user_id = 123 AND created_at > '2024-01-01';  -- Использует индекс
WHERE created_at > '2024-01-01';  -- НЕ использует! (не начинается с user_id)

Правило слева направо: Запрос использует индекс только если начинается с первой колонки в индексе.

Практический пример оптимизации

Без индекса:

SELECT COUNT(*) FROM orders 
WHERE user_id = 123 AND created_at >= '2024-01-01';
-- Full table scan: 5 млн строк проверяются
-- Execution time: 2000ms

С индексом:

CREATE INDEX idx_orders_user_date ON orders(user_id, created_at);

SELECT COUNT(*) FROM orders 
WHERE user_id = 123 AND created_at >= '2024-01-01';
-- Execution time: 5ms

Индекс Covering (Covering Index)

Индекс содержит ВСЕ колонки для ответа на запрос.

-- Обычный индекс
CREATE INDEX idx_user_email ON users(email);
SELECT email, name FROM users WHERE email = 'test@example.com';
-- Найдёт по индексу, но потом полезет в таблицу за name

-- Covering индекс (включает все нужные колонки)
CREATE INDEX idx_user_email_covering ON users(email) INCLUDE (name);
SELECT email, name FROM users WHERE email = 'test@example.com';
-- Всё внутри индекса, не нужна таблица (Index-Only Scan)
-- Execution time: еще быстрее

Когда использовать индекс

Создавай индекс если:

• Колонка часто используется в WHERE
• Таблица большая (>100k строк)
• Запрос медленный (>100ms)
• Колонка имеет низкую кардинальность (мало дубликатов)

НЕ создавай индекс если:

• Таблица маленькая
• Много INSERT/UPDATE (индекс замедляет запись)
• Колонка имеет высокую кардинальность (почти все значения уникальны)
• Запрос уже быстрый

Ловушки индексирования

Проблема 1: Слишком много индексов

CREATE INDEX idx1 ON users(email);
CREATE INDEX idx2 ON users(name);
CREATE INDEX idx3 ON users(created_at);
CREATE INDEX idx4 ON users(status);
-- 4 индекса замедляют INSERT в 4 раза!

Проблема 2: Неправильный порядок в составном индексе

-- Плохо
CREATE INDEX idx ON transactions(created_at, user_id);
SELECT * FROM transactions WHERE user_id = 123;  -- НЕ использует индекс

-- Хорошо
CREATE INDEX idx ON transactions(user_id, created_at);
SELECT * FROM transactions WHERE user_id = 123;  -- Использует индекс

Анализ использования индексов

-- PostgreSQL: какие индексы используются
EXPLAIN (ANALYZE, BUFFERS) 
SELECT * FROM orders WHERE user_id = 123;

-- MySQL: статистика по индексам
SELECT OBJECT_NAME, COUNT_READ, COUNT_INSERT, COUNT_UPDATE, COUNT_DELETE
FROM performance_schema.table_io_waits_summary_by_index_usage
WHERE OBJECT_SCHEMA != 'mysql'
ORDER BY COUNT_READ DESC;

Вывод

Индексирование — это баланс между скоростью чтения и скоростью записи. Правильные индексы могут ускорить запрос в 100+ раз, но плохо спроектированные замедляют систему. Key points:

1. B-Tree для основного использования
2. Hash для точного совпадения
3. Full-Text для текстового поиска
4. Bitmap для низкой кардинальности
5. Spatial для географии
6. Анализируй EXPLAIN перед созданием индекса
7. Удаляй неиспользуемые индексы