В чем сложность работы с хеш-индексом?

# Сложность работы с хеш-индексом в БД

Хеш-индекс — это структура данных для быстрого поиска по точному совпадению. Однако у неё есть серьёзные ограничения и сложности, которые часто забывают при проектировании БД.

Как работает хеш-индекс

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

# Упрощённая модель хеш-индекса
class HashIndex:
    def __init__(self, size=1000):
        self.table = [None] * size
        self.size = size
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        index = self._hash(key)
        self.table[index] = (key, value)  # O(1)
    
    def search(self, key):
        index = self._hash(key)
        if self.table[index] and self.table[index][0] == key:
            return self.table[index][1]  # O(1)
        return None

# Идеально: O(1) для поиска
index = HashIndex()
index.insert('user_123', {'name': 'Alice'})
result = index.search('user_123')  # Очень быстро

Основные сложности

1. Поддерживает только равенство (=)

-- ХОРОШО: хеш-индекс работает
SELECT * FROM users WHERE user_id = 123;

-- ПЛОХО: хеш-индекс НЕ работает
SELECT * FROM users WHERE user_id > 123;        -- Нет
SELECT * FROM users WHERE user_id BETWEEN 100 AND 200;  -- Нет
SELECT * FROM users WHERE user_id IN (1, 2, 3);  -- Нет (некоторые БД)
SELECT * FROM users WHERE user_id LIKE '12%';   -- Нет

-- В этих случаях BTREE индекс намного лучше

2. Нет сортировки данных

-- BTREE индекс может помочь с сортировкой
SELECT * FROM users WHERE user_id > 100 ORDER BY user_id;  -- BTREE работает

-- Хеш-индекс ВСЕГДА требует отдельной сортировки
SELECT * FROM orders WHERE user_id = 123 ORDER BY created_at;  -- Если индекс по user_id
-- Даже если есть хеш-индекс, нужна сортировка в памяти

3. Коллизии (Collision)

Когда два разных ключа дают одинаковый хеш:

class HashIndexWithCollisions:
    def __init__(self, size=10):
        self.table = [[] for _ in range(size)]  # Цепочки для коллизий
        self.size = size
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        index = self._hash(key)
        # Добавляем в цепочку O(1) в среднем, но O(n) в худшем
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))
    
    def search(self, key):
        index = self._hash(key)
        # Ищем в цепочке O(1) в среднем, но O(n) в худшем
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

# Худший случай: все ключи хешируются в один slot
index = HashIndexWithCollisions()
for i in range(1000):
    # Если все хеши одинаковые, O(n) для каждого поиска!
    index.insert(f'key_{i}', i)

4. Масштабирование (Resizing)

Когда индекс заполняется, нужно увеличить размер:

class ResizableHashIndex:
    def __init__(self):
        self.table = [None] * 10
        self.size = 10
        self.count = 0
    
    def insert(self, key, value):
        # Проверяем load factor
        if self.count >= self.size * 0.75:  # 75% filled
            self._resize()  # O(n) операция!
        
        # Нормальная вставка
        index = hash(key) % self.size
        self.table[index] = (key, value)
        self.count += 1
    
    def _resize(self):
        # Масштабирование требует перехеширования всех элементов!
        old_table = self.table
        self.table = [None] * (self.size * 2)
        self.size *= 2
        self.count = 0
        
        for item in old_table:
            if item:
                self.insert(item[0], item[1])

# Операция O(n) когда таблица переполняется
# В среднем редко, но может вызвать spike в production

5. Отсутствие информации о диапазонах

-- Хеш-индекс НЕ может помочь с диапазонными запросами
CREATE INDEX hash_idx ON users USING HASH (age);

-- Эта query будет FULL TABLE SCAN, хотя индекс есть!
SELECT * FROM users WHERE age BETWEEN 20 AND 30;
SELECT * FROM users WHERE age > 25;
SELECT * FROM users WHERE age IN (20, 25, 30);  -- Зависит от БД

-- BTREE индекс работает для всех этих запросов
CREATE INDEX btree_idx ON users (age);
SELECT * FROM users WHERE age BETWEEN 20 AND 30;  -- Index scan!

Сравнение HASH vs BTREE

Практические примеры в разных БД

MySQL

-- InnoDB использует BTREE по умолчанию
CREATE TABLE users (
    id INT PRIMARY KEY,
    username VARCHAR(100) UNIQUE,  -- BTREE индекс
    email VARCHAR(100)
);

-- MEMORY хранилище поддерживает HASH
CREATE TABLE temp_data (
    key_id INT,
    value VARCHAR(255)
) ENGINE=MEMORY;

CREATE INDEX hash_idx ON temp_data (key_id) USING HASH;  -- Хеш-индекс

-- Проблема: IN запрос с хеш-индексом неэффективен
SELECT * FROM temp_data WHERE key_id IN (1, 2, 3);  -- FULL SCAN!

PostgreSQL

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

-- Но есть ограничения:
-- 1. Не может быть многоколонным
CREATE INDEX bad_hash ON orders USING HASH (user_id, order_date);  -- Ошибка!

-- 2. Не поддерживает NULL оптимально
SELECT * FROM users WHERE status IS NULL;  -- Проблемы с хеш-индексом

-- 3. Не может быть частичным (partial index)
CREATE INDEX partial_hash ON users USING HASH (email) 
WHERE status = 'active';  -- Не работает с HASH

-- Для большинства случаев используй BTREE
CREATE INDEX btree_idx ON users (email);  -- Стандартно

SQLite

-- SQLite вообще не поддерживает HASH индексы в стандартном виде
-- Все индексы основаны на BTREE
CREATE INDEX idx ON users (email);  -- Всегда BTREE

Когда хеш-индекс полезен

1. Временные таблицы с точными поисками

from sqlalchemy import Column, Integer, String, Index
from sqlalchemy.ext.declarative import declarative_base

Base = declarative_base()

class TempCache(Base):
    __tablename__ = 'temp_cache'
    
    id = Column(Integer, primary_key=True)
    cache_key = Column(String(255), index=True)  # Может быть HASH
    cache_value = Column(String)
    
    # В MEMORY таблице HASH индекс очень быстрый

2. Очень большие таблицы с точными поисками

-- 100 млн записей, только точные поиски
CREATE TABLE events_cache (
    event_id BIGINT,
    event_data JSONB
);

CREATE INDEX hash_idx ON events_cache USING HASH (event_id);

-- Запросы только такого типа:
SELECT * FROM events_cache WHERE event_id = 12345;  -- Очень быстро

3. Хеш-таблицы в памяти приложения

from collections import defaultdict
import hashlib

# Вместо того чтобы делать JOIN в БД
class HashBasedCache:
    def __init__(self):
        self.data = defaultdict(list)  # Хеш-таблица в памяти
    
    def insert(self, key, value):
        self.data[key].append(value)  # O(1) in memory
    
    def find(self, key):
        return self.data.get(key, [])  # O(1) in memory

# Это намного быстрее, чем индексы в БД

Рекомендации

Используй HASH индекс когда:

• Только точные поиски (=)
• Очень большая таблица
• Нужна максимальная скорость поиска
• Временные данные
• Гарантированно нет диапазонных запросов

Используй BTREE индекс когда:

• Диапазонные запросы (>, <, BETWEEN)
• Нужна сортировка
• Префиксный поиск (LIKE)
• Много разных типов запросов
• Нужна многоколонная индексация
• Стандартный случай (99% случаев)

Тестируй и профилируй:

# Проверь план запроса
explain_output = session.query(User).filter(User.id == 123).explain()
print(explain_output)  # Использует ли индекс?

# Бенчмарк
import time

start = time.time()
for i in range(100000):
    session.query(User).filter(User.id == i).first()
print(f"With hash: {time.time() - start}s")

Итог

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

• Только = операции
• Нет информации о порядке
• Требует масштабирования
• Коллизии могут деградировать производительность

Для 99% случаев BTREE индекс — это оптимальный выбор. Используй HASH только когда ты уверен, что это нужно для конкретной задачи и ты протестировал на реальных данных.