Как оценить алгоритмическую сложность индекса?

Как оценить алгоритмическую сложность индекса?

Сложность индекса — это анализ временной и пространственной эффективности поиска и обновления данных при использовании индекса. Правильная оценка критична для выбора типа индекса и оптимизации производительности БД.

1. B-Tree индекс (стандартный)

Время поиска: O(log N), где N — количество записей Обновление: O(log N) + переиндексирование Пространство: O(N)

import math

#估算 время поиска для B-Tree
def estimate_btree_search_time(num_records):
    # B-Tree обычно имеет order ~100-200
    b_tree_order = 100
    
    disk_seeks = math.log(num_records, b_tree_order)
    # Каждый поиск = ~log_order(N) дисковых операций
    # На SSD ~0.1ms, на HDD ~5ms
    time_ssd = disk_seeks * 0.1  # ms
    time_hdd = disk_seeks * 5    # ms
    
    return {
        'disk_seeks': disk_seeks,
        'time_ssd_ms': time_ssd,
        'time_hdd_ms': time_hdd
    }

result = estimate_btree_search_time(1_000_000)
print(f"Поиск в 1M записей: {result['disk_seeks']:.2f} операций")
print(f"SSD: {result['time_ssd_ms']:.3f}ms, HDD: {result['time_hdd_ms']:.1f}ms")

2. Hash индекс

Время поиска: O(1) среднем случае, O(N) в худшем (collision) Обновление: O(1) среднем Пространство: O(N) Недостаток: не поддерживает range queries

# Hash индекс оптимален для точных поисков
def analyze_hash_index(num_records, load_factor=0.75):
    # Оптимальный размер таблицы
    hash_table_size = num_records / load_factor
    
    # Collision rate
    collision_prob = 1 - (1 - 1/hash_table_size) ** num_records
    
    return {
        'lookup_time': 'O(1)',
        'hash_table_size': hash_table_size,
        'collision_probability': collision_prob,
        'avg_chain_length': load_factor
    }

result = analyze_hash_index(1_000_000)
print(f"Hash индекс для 1M: вероятность collision = {result['collision_probability']:.2%}")

3. Bitmap индекс

Время поиска: O(N/8) для low-cardinality (мало уникальных значений) Обновление: O(1) за запись Пространство: O(distinct_values × N/8) байт Лучше всего: категорийные поля (True/False, страны, статусы)

def estimate_bitmap_index_size(num_records, distinct_values):
    # Один bitmap на каждое значение
    bytes_per_record = 1/8  # 1 бит на запись
    total_size = distinct_values * num_records * bytes_per_record
    
    # B-Tree для сравнения
    btree_size = num_records * 8  # ~8 байт на указатель
    
    return {
        'bitmap_size_mb': total_size / (1024**2),
        'btree_size_mb': btree_size / (1024**2),
        'ratio': btree_size / total_size if total_size > 0 else 0
    }

result = estimate_bitmap_index_size(10_000_000, distinct_values=50)
print(f"Bitmap vs B-Tree для 10M × 50 distinct:")
print(f"Bitmap: {result['bitmap_size_mb']:.1f}MB, B-Tree: {result['btree_size_mb']:.1f}MB")

4. Inverted Index (для полнотекстового поиска)

Время поиска: O(log M) где M — количество уникальных слов Обновление: O(log M) + обновление posting lists Пространство: O(M + total_postings)

def analyze_inverted_index(num_documents, avg_words_per_doc, vocab_size):
    total_postings = num_documents * avg_words_per_doc
    
    # Инвертированный индекс эффективнее на текстовых данных
    # Exemplo: индекс слов вместо индекса каждого символа
    
    return {
        'vocab_size': vocab_size,
        'total_postings': total_postings,
        'postings_per_word': total_postings / vocab_size,
        'search_complexity': 'O(log vocab + postings)',
        'space_complexity': f'O({vocab_size} + {total_postings})'
    }

result = analyze_inverted_index(1_000_000, avg_words_per_doc=100, vocab_size=50_000)
print(f"Inverted Index для 1M документов: {result['postings_per_word']:.0f} posting'ов на слово в среднем")

5. Практическое сравнение: SQL EXPLAIN

-- Анализируем план выполнения
EXPLAIN ANALYZE
SELECT user_id, COUNT(*) 
FROM user_events
WHERE event_type = 'purchase' AND event_date >= '2025-01-01'
GROUP BY user_id;

-- Результат показывает:
-- - Seq Scan vs Index Scan
-- - Количество строк
-- - Actual time vs Estimated time

6. Оценка индекса для разных сценариев

from dataclasses import dataclass
import math

@dataclass
class IndexComplexity:
    name: str
    search_complexity: str
    insert_complexity: str
    space_complexity: str
    use_cases: list
    cardinality: str  # Лучше для высокой/низкой

indexes = [
    IndexComplexity(
        name="B-Tree",
        search_complexity="O(log N)",
        insert_complexity="O(log N)",
        space_complexity="O(N)",
        use_cases=["Range queries", "Sorting", "General purpose"],
        cardinality="High"
    ),
    IndexComplexity(
        name="Hash",
        search_complexity="O(1)",
        insert_complexity="O(1)",
        space_complexity="O(N)",
        use_cases=["Equality searches", "Joins"],
        cardinality="High"
    ),
    IndexComplexity(
        name="Bitmap",
        search_complexity="O(N/8)",
        insert_complexity="O(1)",
        space_complexity="O(distinct × N/8)",
        use_cases=["Low-cardinality", "Boolean filters"],
        cardinality="Low"
    ),
    IndexComplexity(
        name="Full-Text (Inverted)",
        search_complexity="O(log vocab + postings)",
        insert_complexity="O(log vocab)",
        space_complexity="O(vocab + postings)",
        use_cases=["Text search", "Natural language"],
        cardinality="Depends"
    ),
]

for idx in indexes:
    print(f"\n{idx.name}:")
    print(f"  Search: {idx.search_complexity}")
    print(f"  Insert: {idx.insert_complexity}")
    print(f"  Space: {idx.space_complexity}")
    print(f"  Cardinality: {idx.cardinality}")
    print(f"  Use cases: {', '.join(idx.use_cases)}")

7. Алгоритм выбора оптимального индекса

def choose_best_index(query_type, cardinality, data_size, selectivity):
    """
    Selectivity = количество возвращаемых строк / общее количество строк
    """
    
    if query_type == "equality" and selectivity < 0.1:
        return "Hash Index (O(1) lookup)"
    elif query_type == "range":
        return "B-Tree Index (O(log N) + scan)"
    elif cardinality < 100:  # Low-cardinality
        return "Bitmap Index (compact, fast for filters)"
    elif query_type == "text_search":
        return "Inverted Index (Full-text search)"
    elif selectivity > 0.5:  # > 50% rows match
        return "Seq Scan (может быть быстрее индекса)"
    else:
        return "B-Tree Index (default balanced choice)"

# Примеры
print(choose_best_index("equality", 100_000, 1_000_000, 0.05))
print(choose_best_index("range", 100_000, 1_000_000, 0.2))
print(choose_best_index("filter", 50, 1_000_000, 0.1))

Ключевые метрики для оценки индекса

1. Query Time: EXPLAIN ANALYZE в PostgreSQL/MySQL
2. Index Size: занимаемое место на диске
3. Cardinality: количество уникальных значений
4. Selectivity: % строк, соответствующих условию
5. Write Cost: overhead при вставке/обновлении

Правильная оценка сложности позволяет выбрать индекс, который максимизирует производительность для конкретного рабочего нагрузки.