Какая сложность у хэш-индекса?

# Сложность хэш-индекса: полный анализ

Хэш-индекс (Hash Index) — один из основных типов индексов в базах данных. Давайте разберемся с временной сложностью операций и их практическими последствиями.

Временная сложность хэш-индекса

Worst case (редко на практике): O(n) — при полном collision (все ключи хешируются в один bucket)

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

Хэш-индекс использует hash table для быстрого поиска:

# Упрощенное представление как работает Hash Index
class HashIndex:
    def __init__(self):
        self.buckets = {}  # key -> list of row pointers
    
    def insert(self, key, row_pointer):
        hash_value = hash(key)
        if hash_value not in self.buckets:
            self.buckets[hash_value] = []
        self.buckets[hash_value].append(row_pointer)
    
    def search(self, key):
        """O(1) average case"""
        hash_value = hash(key)
        if hash_value in self.buckets:
            return self.buckets[hash_value]  # Обычно 1 элемент
        return None
    
    def range_search(self, start, end):
        """O(n) — нужно проверить все buckets"""
        result = []
        for bucket in self.buckets.values():
            for row_pointer in bucket:
                if start <= row_pointer.key <= end:
                    result.append(row_pointer)
        return result

Примеры в SQL

-- Хэш-индекс ОТЛИЧНО работает для точного поиска:
CREATE INDEX idx_user_email ON users USING HASH (email);
SELECT * FROM users WHERE email = "john@example.com";  -- O(1)

-- Но плохо для диапазонных запросов:
SELECT * FROM users WHERE age > 18;  -- O(n) - не использует индекс!
SELECT * FROM users WHERE name LIKE "John%";  -- O(n) - не использует индекс!

-- И не поддерживает ORDER BY:
SELECT * FROM users WHERE email = "john@example.com" ORDER BY age;  -- O(n log n)

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

✅ Идеально подходит для:

1. Точные поиски по одному столбцу

WHERE user_id = 42
WHERE email = "test@example.com"

1. Join операции на equality

SELECT * FROM orders o
JOIN customers c ON o.customer_id = c.id;  -- O(1) для каждого match

1. Уникальные ограничения (UNIQUE KEY)

CREATE INDEX idx_unique_email ON users (email) USING HASH;

❌ Не подходит для:

1. Диапазонные запросы — O(n)

WHERE price BETWEEN 100 AND 500;  -- Используй B-Tree

1. Сортировка — нет упорядоченности

ORDER BY created_at;  -- Используй B-Tree

1. Prefix searches

WHERE name LIKE "John%";  -- Используй B-Tree

Реальный пример: базовые операции

# PostgreSQL Hash Index пример
"""
CREATE INDEX idx_product_sku ON products USING HASH (sku);
"""

# Поиск по SKU — O(1), очень быстро
SELECT * FROM products WHERE sku = "PROD-12345";  -- ~0.1ms

# Но этот запрос медленный:
SELECT * FROM products WHERE price > 100;  -- ~500ms, сканирует всё

# Правильный индекс для этого:
CREATE INDEX idx_product_price ON products USING BTREE (price);
SELECT * FROM products WHERE price > 100;  -- ~5ms

Почему O(1), а не O(h), где h - размер bucket?

В идеальном хэш-функции и хорошо спроектированной hash table:

1. Load factor поддерживается <= 0.75 — автоматический rehashing
2. Коллизии минимальны — обычно 0-1 элемент в bucket
3. Поиск в bucket — это O(1) операция (linked list с 1 элементом)

# Принцип load factor
load_factor = total_items / number_of_buckets

# Если load_factor > threshold (обычно 0.75):
#   - Увеличиваем количество buckets
#   - Перехешируем все ключи
#   - Теперь O(1) сохраняется

Сравнение с B-Tree индексом

Операция          | Hash Index | B-Tree Index
--------------------------------------------------
Точный поиск      | O(1)       | O(log n)  ✅
Диапазонный поиск | O(n)       | O(log n)  ✅
Сортировка        | O(n)       | O(1)      ✅
Prefix search     | O(n)       | O(log n)  ✅
JOIN на equality  | O(1)       | O(log n)  ✅

Практические советы

1. Используй Hash Index для PRIMARY KEY / UNIQUE KEY:

-- Внутри MySQL будет использовать hash для быстрого поиска
ALTER TABLE users ADD PRIMARY KEY (id) USING HASH;

2. Комбинируй с B-Tree для комплексных запросов:

-- Primary lookup по ID (hash)
CREATE INDEX idx_id USING HASH (user_id);
-- Range filtering (B-Tree)
CREATE INDEX idx_created USING BTREE (created_at);

3. Следи за hash function quality:

# Плохая hash function - много коллизий
def bad_hash(key):
    return len(key)  # Только длина - много коллизий!

# Хорошая hash function - равномерное распределение
# Python использует SipHash - криптографическая, очень хорошая

Заключение

Хэш-индекс имеет O(1) среднюю сложность для точного поиска и становится идеальным выбором для primary keys, уникальных ограничений и equality joins. Однако его неспособность выполнять диапазонные запросы и сортировку за логарифмическое время делает B-Tree более универсальным выбором в большинстве случаев.