Структура
- B‑tree (обычно B+‑tree в СУБД): сбалансированное многоразвильное дерево, узлы вмещают много ключей/указателей, оптимизировано под блочный (дисковый/страничный) доступ. Все листья на одном уровне; внутренние узлы направляют поиск.
- Хэш‑таблица: массив бакетов + хеш‑функция; коллизии решаются цепочками (chaining) или открытой адресацией. Нет порядка ключей.
Сложность операций (поиск / вставка / удаление)
- B‑tree:
- поиск/вставка/удаление: $\mathcal{O}({\log }_{m}n)$ по числу узлов ≈ $\mathcal{O}(\log n)$, где $m$ — минимальный/максимальный фактор развилки. На практике число дисковых чтений ≈ высота дерева (малое).
- при вставке возможны разделения узлов (amortized cost остаётся логарифмическим).
- Хэш‑таблица:
- среднее время поиска/вставки/удаления: $\mathcal{O}(1)$ (точнее $\mathcal{O}(1+\alpha )$, где $\alpha$ — load factor).
- худший случай (плохая хеш‑функция или атакующие входные данные): $\mathcal{O}(n)$.
- при динамическом расширении — рехеширование (амортизированно остаётся $\mathcal{O}(1)$, но может быть дорогая операция).
Устойчивость к распределению данных
- B‑tree:
- независимо от распределения ключей поддерживает баланс; стабильная производительность для равномерных и скошенных данных.
- хорош для упорядоченных последовательных вставок (часто оптимизированы для этого; возможно влияние split pattern).
- Хэш‑таблица:
- производительность сильно зависит от качества хеш‑функции и load factor. При плохой хеш‑функции (или специально сконструированных ключах) возможны долгие цепочки — деградация до $\mathcal{O}(n)$.
- для реальных широких распределений при хорошей функции даёт быстрый доступ; для последовательных/скученных ключей нужно спектр распределения через хеш.
Дополнительные свойства (порядок, диапазонные запросы, локальность)
- B‑tree:
- сохраняет порядок ключей → эффективны range‑запросы, сортировка, соседние/префиксные запросы.
- оптимизирован под блочную локальность (узел = страница) → мало дисковых операций.
- поддержка итераторов и диапазонной блокировки (важно в СУБД для транзакций).
- Хэш‑таблица:
- не поддерживает эффективные range‑запросы или «следующий ключ».
- плохая кэш‑локальность при случайных размещениях ключей; в памяти — быстрые точечные доступы.
- чувствительна к конкурентному доступу (можно шардировать по бакетам).
Применимость и практические примеры
- Базы данных:
- B+‑tree — стандартный выбор для первичных/вторичных индексов, где нужны range‑scan, ORDER BY, BETWEEN, сортировки и гарантия стабильной производительности (пример: MySQL InnoDB, PostgreSQL — B‑tree по умолчанию).
- Хэш‑индексы полезны для быстрых точечных равенств (например, exact lookup), но неудобны для диапазонов; в некоторых СУБД поддерживаются, но с ограничениями (жёсткая зависимость от реализации и логирования).
- Файловые системы:
- B‑tree/B+‑tree широко используются для каталогов и метаданных (NTFS, HFS+, Btrfs) из‑за упорядоченности и эффективного блочного доступа.
- Хеширование применяется иногда для быстрого поиска в директориях (например, HTree в ext3 — разновидность хеширования директорий), но обычно как часть гибридных структур.
- Кэши и in‑memory задачи:
- Хэш‑таблицы — стандарт для in‑memory кэшей и быстрых сопоставлений ключ→значение (memcached, словари в языках). Часто комбинируются с LRU‑списком для политик вытеснения.
- B‑tree редко применяется для простых in‑memory кэшей, но полезен если нужно ordered iteration или диапазонные удаления.
- Хранилища и индексные структуры на диске:
- B‑tree хорош для OLTP и систем с частыми точечными и диапазонными запросами.
- Для высокопроизводительных запись‑ориентированных хранилищ часто используют LSM‑деревья (log‑structured merge), которые совмещают преимущества последовательных записей и асинхронной слияния — это альтернатива B‑tree для интенсивных вставок (пример: LevelDB, RocksDB).
Практические рекомендации (когда выбирать)
- Выберите B‑tree, если нужно:
- диапазонные запросы, сортировка, итерация по ключам;
- предсказуемая производительность на диске/SSD;
- поддержка транзакционной семантики и блокировок диапазонов.
- Выберите хэш‑таблицу, если нужно:
- максимально быстрые точечные (equality) запросы в памяти;
- простота реализации и нет необходимости в порядке ключей;
- можно контролировать и/или случайно распределять ключи (хеш качественный).
- Для дисковых хеш‑структур (extendible/linear hashing) — когда нужен быстрый equality lookup на диске и ожидается частая динамическая смена объёма — но обычно сложнее обеспечить транзакционность и range‑функции.
Короткое сводное сравнение (сложности)
- B‑tree: поиск/вставка/удаление $\mathcal{O}(\log n)$, хорош для диапазонов, устойчива к распределению.
- Хэш‑таблица: среднее $\mathcal{O}(1)$ (точечные), худшее $\mathcal{O}(n)$, плохо для range, чувствительна к хеш‑функции.
Если нужно, могу привести конкретные примеры выбора структур для заданных сценариев (OLTP индекс / каталог файловой системы / in‑memory кэш).