Какая сложность выполнения запросов к хэш-таблицы B-Tree?

Сложность выполнения запросов к хэш-таблице и B-Tree

Это два основных способа организации данных в СУБД и структурах данных. Они имеют разную сложность для разных операций.

Хэш-таблица (Hash Table)

Структура: массив с функцией хэширования. Размер O(n).

Хэш-таблица:
┌─────┬─────┬─────┬─────┬─────┐
│ ∅   │ key2→val2 │ key3→val3 │ ∅ │ key1→val1 │
└─────┴─────┴─────┴─────┴─────┘

Временная сложность:

Худший случай происходит при коллизиях хэшей (когда много ключей хэшируются в один индекс).

Пример реализации:

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        index = self._hash(key)
        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))  # O(1) в среднем
    
    def search(self, key):
        index = self._hash(key)
        for k, v in self.table[index]:  # O(1) в среднем, O(n) в худшем
            if k == key:
                return v
        return None

Когда используется:

• Python dict и set
• Redis
• Memcached
• HashMap в Java

B-Tree

Структура: сбалансированное дерево поиска. Размер O(log n).

         [30, 70]
        /    |     \
    [10,20] [40,60] [80,90]

Временная сложность:

k — количество элементов в диапазоне.

Пример B-Tree операций:

class BTreeNode:
    def __init__(self, leaf=True):
        self.keys = []
        self.children = []
        self.leaf = leaf
    
    def search(self, key):
        # O(log n) — находится за логарифм от высоты дерева
        i = 0
        while i < len(self.keys) and key > self.keys[i]:
            i += 1
        
        if i < len(self.keys) and key == self.keys[i]:
            return True
        
        if self.leaf:
            return False
        
        return self.children[i].search(key)

class BTree:
    def search(self, key):
        # O(log n)
        return self.root.search(key)
    
    def insert(self, key):
        # O(log n)
        # ... split nodes if needed
        pass
    
    def range_query(self, min_key, max_key):
        # O(log n + k) где k — результаты
        results = []
        # ... traverse and collect
        return results

Когда используется:

• Индексы в PostgreSQL, MySQL
• Файловые системы (NTFS, ext4)
• Базы данных (почти все используют B+ деревья)

Прямое сравнение

1. Поиск ключа

Хэш-таблица:

# O(1) в среднем
d = {'name': 'John', 'age': 30}
value = d['name']  # Очень быстро

B-Tree:

-- O(log n)
SELECT value FROM users WHERE id = 5;  -- Быстро, но не O(1)

2. Range query

Хэш-таблица:

# O(n) — нужно проверить все элементы
results = [v for k, v in hash_table if 10 <= k <= 20]

B-Tree:

-- O(log n + k) где k = результаты
SELECT * FROM users WHERE age BETWEEN 20 AND 30;  -- Очень эффективно

3. Сортировка

Хэш-таблица:

# O(n log n) — нужно сортировать результаты
sorted_items = sorted(hash_table.items())

B-Tree:

-- O(k) если элементы упорядочены
SELECT * FROM users ORDER BY created_at LIMIT 10;  -- Очень быстро

Пространственная сложность

Оба требуют O(n) памяти, но B-Tree использует больше из-за указателей на дочерние узлы.

Производительность на практике

Hash Table (Python dict):

import time

d = {i: i*2 for i in range(1_000_000)}

# Поиск — O(1)
start = time.time()
for i in range(1_000_000):
    _ = d[i]
print(f"Hash table lookup: {time.time() - start:.3f}s")  # ~0.05s

# Range query — O(n)
start = time.time()
results = [v for k, v in d.items() if 500_000 <= k <= 501_000]
print(f"Range query: {time.time() - start:.3f}s")  # ~0.2s

B-Tree (индекс БД):

-- Поиск O(log n)
EXPLAIN ANALYZE SELECT * FROM huge_table WHERE id = 500000;
-- Index Scan: ~0.1ms

-- Range query O(log n + k)
EXPLAIN ANALYZE SELECT * FROM huge_table WHERE id BETWEEN 500000 AND 501000;
-- Index Scan: ~1ms (очень быстро)

Коллизии в хэш-таблице

Качество хэш-функции критично:

# Плохая хэш-функция
def bad_hash(key):
    return 0  # Все ключи в одном бакете

# Результат:
# Insert: O(1) → O(n) при каждом insert
# Search: O(1) → O(n) при поиске

# Хорошая хэш-функция (встроенная в Python)
d = {}
for i in range(1_000_000):
    d[i] = i  # O(1) амортизированно

Выводы

Выбери хэш-таблицу если:

• Нужны частые поиски по точному ключу (O(1) vs O(log n))
• Нет range queries
• Нет требований к сортировке
• Нужна максимальная скорость для point lookups

Выбери B-Tree если:

• Нужны range queries (O(log n + k) vs O(n))
• Нужна упорядоченность данных
• Нужны операции: min, max, between
• Работаешь с дисковыми данными (лучше локальность)

В СУБД

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

1. Range queries более важны чем point lookups
2. Упорядоченность помогает с сортировкой и группировкой
3. Лучше работают с дисковыми операциями (кэширование)