Является ли хеш-индекс самым простым?

Хеш-индекс: простота и сложность

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

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

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

• Хеш-таблица: массив "корзин" (buckets)
• Хеш-функция: преобразует значение ключа в индекс массива
• Разрешение коллизий: обработка ситуаций, когда разные ключи дают одинаковый хеш

Вход: ключ = 42
Хеш-функция: hash(42) % size = 5
Результат: обращение к bucket[5] → найти ссылку на строку

Преимущества хеш-индекса

Скорость точного поиска

• Временная сложность: O(1) в среднем случае
• Прямое обращение к памяти без сканирования множества значений

-- Поиск по хеш-индексу
SELECT * FROM users WHERE id = 42;  -- O(1)

Простота реализации

• Не требует сложных структур данных (как B-дерево)
• Прямое вычисление позиции элемента

Эффективность для точного совпадения

• Идеален для поиска по первичному ключу
• Быстрые JOIN операции

Недостатки и ограничения

1. Невозможность диапазонных запросов

Хеш-индекс не сохраняет порядок, поэтому диапазонные запросы невозможны:

-- Это НЕ использует хеш-индекс эффективно
SELECT * FROM users WHERE age > 18;  -- Полное сканирование таблицы
SELECT * FROM users WHERE salary BETWEEN 5000 AND 10000;  -- Неэффективно

Для B-дерева индекса это работает за O(log n) + результаты:

-- С B-дерево индексом — быстро
SELECT * FROM users WHERE age > 18;  -- O(log n) поиск + scan результатов

2. Не поддерживает сортировку

-- Хеш-индекс не помогает с сортировкой
SELECT * FROM users WHERE id = 42 ORDER BY name;  -- Требует отдельной сортировки

3. Нестабильность при изменении размера таблицы

Когда хеш-таблица заполняется, требуется rehashing (пересчёт всех хешей):

# Пример rehashing
class HashIndex:
    def __init__(self, size=10):
        self.size = size
        self.buckets = [[] for _ in range(size)]
        self.count = 0
    
    def insert(self, key, value):
        if self.count >= self.size * 0.75:  # Load factor
            self._rehash()  # Пересчёт всех хешей!
        
        index = hash(key) % self.size
        self.buckets[index].append((key, value))
        self.count += 1
    
    def _rehash(self):
        """Дорогостоящая операция"""
        old_buckets = self.buckets
        self.size *= 2
        self.buckets = [[] for _ in range(self.size)]
        self.count = 0
        
        for bucket in old_buckets:
            for key, value in bucket:
                self.insert(key, value)  # Пересчёт хешей

4. Проблема коллизий

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

class HashIndexWithCollisions:
    def __init__(self, size=10):
        self.buckets = [[] for _ in range(size)]
    
    def insert(self, key, value):
        index = hash(key) % len(self.buckets)
        # Линейное разрешение коллизий
        for i, (k, v) in enumerate(self.buckets[index]):
            if k == key:
                self.buckets[index][i] = (key, value)
                return
        self.buckets[index].append((key, value))
    
    def search(self, key):
        index = hash(key) % len(self.buckets)
        for k, v in self.buckets[index]:  # Линейный поиск в bucket
            if k == key:
                return v
        return None

При плохой хеш-функции коллизии деградируют производительность до O(n).

5. Только равенство, не сравнение

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

-- НЕ работает эффективно
SELECT * FROM users WHERE id < 100;  -- Требует полного сканирования
SELECT * FROM users WHERE id <> 42;  -- Требует полного сканирования

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

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

Идеальные сценарии:

• Точный поиск по первичному ключу
• Поиск в таблице с огромным количеством строк (миллионы)
• Системы, требующие максимальной скорости поиска за счёт диапазонных запросов

-- Примеры, где хеш-индекс идеален
CREATE INDEX idx_user_id ON users USING HASH(id);
CREATE INDEX idx_session ON sessions USING HASH(session_key);

-- Очень быстро
SELECT * FROM users WHERE id = 42;
SELECT * FROM sessions WHERE session_key = 'abc123';

Когда НЕ использовать:

• Когда нужны диапазонные запросы
• Когда нужна сортировка результатов
• Когда часто используются операции сравнения (<, >, <=, >=)

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

from collections import defaultdict

class UserDatabase:
    def __init__(self):
        # Хеш-индекс по ID
        self.users_by_id = {}
        # B-дерево-подобный индекс по возрасту (отсортированный)
        self.users_by_age = defaultdict(list)
    
    def add_user(self, user_id, name, age):
        user = {'id': user_id, 'name': name, 'age': age}
        
        # Хеш-индекс — очень быстро
        self.users_by_id[user_id] = user
        
        # Индекс по возрасту
        self.users_by_age[age].append(user)
    
    def find_by_id(self, user_id):
        """O(1) — хеш-индекс"""
        return self.users_by_id.get(user_id)
    
    def find_by_age_range(self, min_age, max_age):
        """O(n) с хеш, O(log n + результаты) с B-дерево"""
        result = []
        for age in range(min_age, max_age + 1):
            result.extend(self.users_by_age[age])
        return result

db = UserDatabase()
db.add_user(1, "Alice", 25)
db.add_user(2, "Bob", 30)
db.add_user(3, "Charlie", 25)

print(db.find_by_id(1))  # O(1) — очень быстро
print(db.find_by_age_range(25, 28))  # O(n) — медленнее

Заключение

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