Почему B-Ttree индекс используется чаще, чем хеш-индекс несмотря на то, что он медленнее, чем хеш-индекс?

# Почему B-Tree индекс используется чаще, чем хеш-индекс несмотря на то, что он медленнее?

Это отличный вопрос, который демонстрирует глубокое понимание структур данных. B-Tree индексы действительно медленнее для поиска конкретного значения, но имеют критические преимущества, которые делают их предпочтительными в подавляющем большинстве случаев.

1. Поддержка диапазонных запросов

Хеш-индекс отлично подходит только для точных поисков (equality search). Для диапазонных запросов хеш-индекс практически бесполезен.

-- Работает хорошо с B-Tree, неэффективно с хеш-индексом
SELECT * FROM users WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31';
SELECT * FROM products WHERE price > 100 AND price < 500;
SELECT * FROM posts WHERE views >= 1000;

Хеш-индекс должен был бы просканировать ВСЕ значения, так как хеширование уничтожает порядок данных. B-Tree сохраняет отсортированный порядок и может эффективно навигировать по диапазонам.

2. Сортировка результатов

B-Tree естественным образом поддерживает сортировку благодаря своей упорядоченной структуре. Хеш-индекс не может помочь с ORDER BY.

-- Очень эффективно с B-Tree
SELECT * FROM orders 
ORDER BY order_date DESC 
LIMIT 10;

-- С хеш-индексом придётся сортировать в памяти
SELECT * FROM orders 
WHERE customer_id = 123 
ORDER BY created_at;

3. Prefix-запросы (LIKE, ILIKE)

Для текстового поиска по префиксу B-Tree индекс может быстро найти диапазон начинающихся с нужной последовательности.

-- B-Tree ищет всех пользователей с именем на "Jo"
SELECT * FROM users WHERE name LIKE 'Jo%';

-- Хеш-индекс не может использовать prefix-поиск
-- Придётся полностью сканировать таблицу

4. Составные индексы

B-Tree дает гибкость с составными индексами.

CREATE INDEX idx_user_date ON orders(user_id, order_date);

-- Можно использовать по первому полю
SELECT * FROM orders WHERE user_id = 5;

-- Или по обоим полям
SELECT * FROM orders WHERE user_id = 5 AND order_date > '2024-01-01';

-- С хеш-индексом требуется точное совпадение ВСЕХ полей

5. NULL значения и IN оператор

-- B-Tree хорошо работает с NULL (он всегда слева в B-Tree)
SELECT * FROM products WHERE category IS NULL;

-- IN оператор лучше с B-Tree
SELECT * FROM users WHERE status IN ('active', 'pending', 'archived');

Сравнение характеристик

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

import psycopg2
from psycopg2 import sql

conn = psycopg2.connect("dbname=mydb user=postgres")
cursor = conn.cursor()

# Создание таблицы
cursor.execute("""
    CREATE TABLE IF NOT EXISTS events (
        id SERIAL PRIMARY KEY,
        user_id INTEGER,
        event_date TIMESTAMP,
        event_type VARCHAR(50),
        value DECIMAL
    )
""")

# B-Tree индекс (по умолчанию)
cursor.execute("CREATE INDEX idx_user_date ON events(user_id, event_date)")

# Хеш-индекс (редко используется)
cursor.execute("CREATE INDEX idx_event_type_hash ON events USING HASH (event_type)")

conn.commit()

# Запросы, которые работают хорошо с B-Tree
queries = [
    # Диапазон дат
    "SELECT * FROM events WHERE event_date >= '2024-01-01'",
    # Сортировка
    "SELECT * FROM events WHERE user_id = 1 ORDER BY event_date DESC",
    # Prefix + диапазон
    "SELECT * FROM events WHERE user_id BETWEEN 100 AND 200 AND event_date > '2024-06-01'",
    # IN с множеством значений
    "SELECT * FROM events WHERE user_id IN (1, 2, 3, 5, 8, 13, 21)"
]

for query in queries:
    cursor.execute(f"EXPLAIN {query}")
    print(cursor.fetchall())

conn.close()

Когда используются хеш-индексы?

Хеш-индексы применяют в редких случаях:

1. Специальные структуры (например, in-memory БД как Redis)
2. Точные поиски по огромным таблицам когда O(1) критичнее O(log N)
3. Распределённые системы (consistent hashing для partition key)

Вывод

B-Tree индексы доминируют потому что они универсальны:

• ✅ Отлично работают для точных поисков
• ✅ Поддерживают диапазонные запросы
• ✅ Помогают с сортировкой
• ✅ Работают с LIKE, BETWEEN, IN
• ✅ Flexible для составных индексов

Хеш-индексы — узкоспециализированный инструмент для очень специфических случаев. В реальной практике разработчик встретит B-Tree в 99% случаев.