Какие плюсы и минусы хеш индекса в БД?

Плюсы и минусы хеш индекса в БД

Хеш индекс (hash index) — это важная тема, которую часто недооценивают. Многие разработчики используют индексы неправильно, потому что не понимают их характеристики. Это может привести к неожиданной медленности production систем.

1. Что такое хеш индекс

Хеш индекс использует хеш-функцию для быстрого поиска по точному значению:

-- PostgreSQL
CREATE INDEX idx_email ON users USING HASH (email);

-- MySQL
CREATE INDEX idx_email ON users (email);

-- SQLite
CREATE INDEX idx_email ON users(email);

-- Поиск: очень быстро O(1) в среднем
SELECT * FROM users WHERE email = 'ivan@example.com';

Внутренняя структура:

Хеш таблица:
[0] → email1 → id1
[1] → email2 → id2
[2] → (пусто)
[3] → email3 → id3
...

Поиск 'email1':
1. Вычислить хеш('email1') = 0
2. Посмотреть позицию [0]
3. Вернуть id1
Время: O(1) в среднем

2. Плюсы хеш индекса

2.1 Очень быстрый поиск по точному значению

-- Поиск по ID: O(1) время
SELECT * FROM users WHERE id = 42;

-- Без индекса: O(n) полное сканирование
-- С хеш индексом: O(1) прямой доступ

-- Разница на 10 млн записей:
-- Без индекса: 10 млн операций
-- С индексом: ~1 операция

Практический пример:

# Python ORM (SQLAlchemy)
session.query(User).filter(User.id == 42).first()
# С индексом: быстро (1 операция)
# Без индекса: медленно (10 млн операций)

2.2 Экономия памяти

Хеш индекс занимает меньше места чем B-Tree:

-- B-Tree индекс (по умолчанию)
CREATE INDEX idx_email_btree ON users USING BTREE (email);
-- Размер: может быть 100+ MB для 10 млн записей

-- Хеш индекс
CREATE INDEX idx_email_hash ON users USING HASH (email);
-- Размер: может быть 50 MB для 10 млн записей (примерно в 2 раза меньше)

2.3 Простота: нет упорядочения

Легче реализовать хеш индекс:

-- B-Tree требует поддержку упорядочения
SELECT * FROM users WHERE email >= 'a' AND email <= 'z'
-- Работает со сложной структурой

-- Хеш индекс просто индексирует значения
-- Поэтому хеш индекс быстрее создавать и обновлять

3. Минусы хеш индекса

3.1 Не работает для range queries (диапазонные запросы)

Это ОСНОВНОЙ недостаток:

-- ✅ Работает хорошо
SELECT * FROM users WHERE id = 42;

-- ❌ Хеш индекс бесполезен для range queries
SELECT * FROM users WHERE id > 100 AND id < 200;
-- Нужно отсканировать ВСЕ записи!

-- ❌ Не работает с операторами
SELECT * FROM users WHERE email LIKE 'ivan%';
-- Хеш индекс не помогает

-- ❌ Сортировка не использует хеш индекс
SELECT * FROM users ORDER BY email;
-- Даже если есть индекс, нужно сортировать

Примеры проблемных запросов:

-- Все эти запросы НЕ используют хеш индекс:

WHERE created_at >= '2024-01-01'     -- range
WHERE price < 1000                    -- range
WHERE name LIKE '%john%'              -- LIKE
WHERE status IN (1, 2, 3)             -- IN (иногда)
ORDER BY created_at                   -- сортировка
GROUP BY category                     -- группировка

3.2 Необходимость B-Tree для сортировки

# Django ORM
from django.db import models

class Product(models.Model):
    price = models.IntegerField(db_index=True)  # По умолчанию B-Tree

# Запрос с сортировкой
Product.objects.filter(price=100).order_by('price')
# Индекс помогает с фильтром, но НЕ помогает с сортировкой

# Запрос с диапазоном
Product.objects.filter(price__gte=100, price__lte=500)
# Хеш индекс бесполезен
# Нужен B-Tree индекс

3.3 Хеш коллизии (hash collisions)

Несколько значений могут иметь одинаковый хеш:

-- Идеальный случай: каждый хеш указывает на одно значение
-- Реальность: иногда коллизии

hash('email1') = 12345
hash('email999') = 12345  -- Коллизия!

-- БД должна разрешить коллизию (chaining)
-- Это замедляет поиск с O(1) до O(k), где k = количество коллизий

Чем больше данных, тем больше вероятность коллизий:

# На 10 млн записей хеш индекс может деградировать
# с O(1) до O(10) в худшем случае

3.4 Постоянная перестройка при изменении размера

-- При добавлении новых записей хеш индекс может перестроиться
-- (зависит от БД)

INSERT INTO users (email) VALUES ('new@example.com');
-- Иногда нужен REBALANCE хеш таблицы

-- Это блокирует таблицу на время операции
-- В production это может быть критично

3.5 Не подходит для FOREIGN KEY

-- ❌ Проблема с внешними ключами
ALTER TABLE orders ADD CONSTRAINT fk_user_id
  FOREIGN KEY (user_id) REFERENCES users(id);

-- Если индекс на users(id) — хеш индекс
-- При удалении пользователя БД должна проверить все заказы
-- Хеш индекс не помогает для этой проверки

3.6 Не поддерживается всеми БД

-- PostgreSQL: поддерживает HASH индекс
CREATE INDEX idx_email ON users USING HASH (email);

-- MySQL: не поддерживает явно, но использует хеш для MEMORY таблиц
CREATE TABLE cache USING MEMORY (
    id INT PRIMARY KEY,
    value VARCHAR(255)
);

-- SQLite: не поддерживает явно

-- MongoDB: не использует хеш индексы

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

-- ✅ ХОРОШО: точный поиск по ID
CREATE INDEX idx_user_id ON orders USING HASH (user_id);
SELECT * FROM orders WHERE user_id = 42;

-- ✅ ХОРОШО: точный поиск по email (уникальный)
CREATE INDEX idx_email ON users USING HASH (email);
SELECT * FROM users WHERE email = 'ivan@example.com';

-- ✅ ХОРОШО: поиск по uuid
CREATE INDEX idx_session_id ON sessions USING HASH (session_id);
SELECT * FROM sessions WHERE session_id = 'abc123def456';

-- ✅ ХОРОШО: поиск по хешу пароля
CREATE INDEX idx_password_hash ON users USING HASH (password_hash);
SELECT * FROM users WHERE password_hash = sha256('password');

5. Когда использовать B-Tree

-- ✅ ЛУЧШИЙ ВЫБОР: большинство случаев
CREATE INDEX idx_email ON users (email);  -- B-Tree по умолчанию

-- ✅ ОБЯЗАТЕЛЬНО для range queries
CREATE INDEX idx_created_at ON posts (created_at);
SELECT * FROM posts WHERE created_at >= '2024-01-01';

-- ✅ ОБЯЗАТЕЛЬНО для сортировки
CREATE INDEX idx_price ON products (price);
SELECT * FROM products ORDER BY price;

-- ✅ ОБЯЗАТЕЛЬНО для LIKE запросов
CREATE INDEX idx_name ON users (name);
SELECT * FROM users WHERE name LIKE 'ivan%';

-- ✅ ОБЯЗАТЕЛЬНО для FOREIGN KEY
CREATE INDEX idx_user_id ON orders (user_id);
ALTER TABLE orders ADD CONSTRAINT fk_user_id
  FOREIGN KEY (user_id) REFERENCES users(id);

6. Практический пример

# Django ORM
from django.db import models

class User(models.Model):
    id = models.BigAutoField(primary_key=True)
    email = models.EmailField(unique=True)  # Уникальный, точный поиск
    username = models.CharField(max_length=100)
    created_at = models.DateTimeField(auto_now_add=True)  # Range queries
    is_active = models.BooleanField(default=True)
    
    class Meta:
        indexes = [
            # ✅ ПРАВИЛЬНО для точного поиска
            # models.Index(fields=['email'], name='idx_email_hash'),
            # Но Django не поддерживает явно HASH индексы
            # Используется B-Tree (значение по умолчанию)
            
            # ✅ Составной индекс для range queries
            models.Index(fields=['is_active', 'created_at'], name='idx_active_created'),
            
            # ❌ Не помогает
            # models.Index(fields=['created_at'], name='idx_created_hash_wrong'),
        ]

# Оптимальные запросы:
User.objects.filter(email='ivan@example.com')  # Быстро (B-Tree индекс)
User.objects.filter(
    created_at__gte='2024-01-01',
    is_active=True
).order_by('created_at')  # Быстро (составной B-Tree индекс)

# Неоптимальные запросы:
User.objects.filter(username__icontains='ivan')  # Медленно (нет индекса на LIKE)
User.objects.filter(created_at__year=2024)  # Может быть медленным

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

Best Practice

• По умолчанию: используй B-Tree индекс (это дефолт в большинстве БД)
• Для точного поиска: B-Tree тоже хорош, но хеш немного быстрее (разница минимальна)
• Для диапазонов: ТОЛЬКО B-Tree или другие индексы
• Для LIKE: ТОЛЬКО B-Tree
• В production: сначала профилируй запросы, потом добавляй индексы
• Помни: индекс требует памяти и замедляет INSERT/UPDATE/DELETE

Хеш индекс — специализированный инструмент. Используй его только если ты уверен, что точно знаешь что делаешь!