В чем разница между B-tree и Hash индексами?

# B-tree и Hash индексы: сравнение

Выбор правильного типа индекса критически влияет на производительность базы данных. B-tree и Hash индексы имеют разные характеристики и предназначены для разных сценариев использования.

B-tree индексы

B-tree (сбалансированное дерево) - это самый универсальный и часто используемый тип индекса в большинстве СУБД.

Структура:

• Дерево остаётся сбалансированным
• Узлы содержат отсортированные значения ключей
• Листья содержат указатели на строки данных
• Глубина дерева O(log n)

// Пример B-tree структуры (концептуально)
/*
           [50]
          /    \
       [20]    [70]
      /  \    /  \
   [10][30][60][80]
*/

Преимущества:

• Поддерживает диапазонные запросы (BETWEEN, >, <)
• Поддерживает сортировку (ORDER BY)
• Эффективен для поиска по префиксу (LIKE abc%)
• Хороший баланс между чтением и записью
• Универсален для всех типов данных
• Поддерживает NULL значения

Недостатки:

• Медленнее чем Hash для точного поиска (equality)
• Требует больше дисковых операций для поиска

Использование:

CREATE INDEX idx_users_email ON users(email);
-- По умолчанию создаётся B-tree индекс

-- B-tree оптимален для таких запросов:
SELECT * FROM users WHERE email = test@example.com; -- Точный поиск
SELECT * FROM users WHERE email LIKE test%; -- Поиск по префиксу
SELECT * FROM orders WHERE created_at > 2024-01-01; -- Диапазонный поиск
SELECT * FROM products ORDER BY price; -- Сортировка
SELECT * FROM users WHERE age BETWEEN 20 AND 30; -- Диапазон

Hash индексы

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

Структура:

• Хеш-функция преобразует значение ключа в адрес
• Таблица хеширования с корзинами (buckets)
• O(1) временная сложность для точного поиска

// Концептуальная структура Hash индекса
/*
Лучшее хеширование:
key: "john@example.com" -> hash -> bucket 15 -> row_id
key: "jane@example.com" -> hash -> bucket 42 -> row_id
*/

Преимущества:

• Очень быстрый поиск по точному значению O(1)
• Меньше дисковых операций
• Простая структура

Недостатки:

• Не поддерживает диапазонные запросы
• Не поддерживает сортировку (ORDER BY)
• Не работает с LIKE или частичным поиском
• Проблемы с коллизиями при плохой хеш-функции
• Не поддерживает NULL значения (в некоторых СУБД)
• Дорогостоящее перестроение при переполнении
• Не использует индекс при изменении структуры таблицы

Использование:

-- Синтаксис зависит от СУБД (не все поддерживают)
-- MySQL (MEMORY, InnoDB с ограничениями):
CREATE INDEX idx_users_id USING HASH ON users(user_id);

-- Hash индекс работает только для точного поиска:
SELECT * FROM users WHERE id = 123; -- Отлично
SELECT * FROM users WHERE id > 123; -- НЕ использует Hash индекс!
SELECT * FROM users WHERE name LIKE John%; -- НЕ работает
SELECT * FROM users ORDER BY age; -- НЕ работает

Таблица сравнения

Практический пример Java приложения

public class UserRepository {
    private DataSource dataSource;
    
    // Эффективно использует B-tree индекс
    public User findByEmail(String email) throws SQLException {
        String sql = "SELECT * FROM users WHERE email = ?"; // Точный поиск
        try (Connection conn = dataSource.getConnection();
             PreparedStatement stmt = conn.prepareStatement(sql)) {
            stmt.setString(1, email);
            ResultSet rs = stmt.executeQuery();
            if (rs.next()) {
                return mapResultSetToUser(rs);
            }
        }
        return null;
    }
    
    // Диапазонный запрос - ТРЕБУЕТ B-tree
    public List<User> findByAgeRange(int minAge, int maxAge) throws SQLException {
        String sql = "SELECT * FROM users WHERE age BETWEEN ? AND ? ORDER BY age";
        // Hash индекс НЕ помогает здесь!
        // Нужен B-tree индекс на column age
        
        List<User> users = new ArrayList<>();
        try (Connection conn = dataSource.getConnection();
             PreparedStatement stmt = conn.prepareStatement(sql)) {
            stmt.setInt(1, minAge);
            stmt.setInt(2, maxAge);
            ResultSet rs = stmt.executeQuery();
            while (rs.next()) {
                users.add(mapResultSetToUser(rs));
            }
        }
        return users;
    }
    
    // Поиск по префиксу - ТРЕБУЕТ B-tree
    public List<User> findByEmailPrefix(String prefix) throws SQLException {
        String sql = "SELECT * FROM users WHERE email LIKE ? ORDER BY email";
        // Hash индекс полностью бесполезен!
        
        List<User> users = new ArrayList<>();
        try (Connection conn = dataSource.getConnection();
             PreparedStatement stmt = conn.prepareStatement(sql)) {
            stmt.setString(1, prefix + "%");
            ResultSet rs = stmt.executeQuery();
            while (rs.next()) {
                users.add(mapResultSetToUser(rs));
            }
        }
        return users;
    }
}

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

B-tree:

• Общие случаи (используй по умолчанию)
• Диапазонные запросы
• Сортировка данных
• Поиск по префиксу
• Составные индексы

Hash:

• Только частые точные поиски по одному полю
• Когда скорость критична и диапазоны не нужны
• IN-clause с конкретными значениями

Заключение

B-tree индекс - универсальный выбор для большинства случаев. Hash индекс полезен для специфических сценариев с высокими требованиями к скорости точного поиска. В современных СУБД B-tree часто доминирует из-за его гибкости.